|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
05.12.2012, 22:18 | #11 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
"Запросы с любыми комбинациями И/ИЛИ/НЕ на любые характеристики (а их 10 000 для типичного пользователя)"
Т.е. чисто гипотетически в запросе м.б. тысячи логических условий
Благими намерениями устлана дорога на programmersforum.ru
|
05.12.2012, 22:22 | #12 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
05.12.2012, 22:26 | #13 | |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Цитата:
Благими намерениями устлана дорога на programmersforum.ru
|
|
05.12.2012, 22:26 | #14 | |||
Пользователь
Регистрация: 04.10.2012
Сообщений: 95
|
Цитата:
Цитата:
Цитата:
В целом спасибо, особенно Abstraction. Не будет такого падения производительности как у меня сейчас при сложных условиях.
Пишу на чистом С, плюсы спилил.
|
|||
05.12.2012, 22:44 | #15 | ||||||
Пользователь
Регистрация: 04.10.2012
Сообщений: 95
|
Цитата:
Цитата:
1. Создать массив указателей и числовых значений. 2. Заполнить эти числовые значения в соотв. с условием. 3. Отсортировать и выбрать наиболее подходящие. Цитата:
Ограничений я не ставил, хотя в принципе их нет, но они будут набиваться пользователем, редко когда будет больше 10, а чаще всего простая выборка по одной характеристике. Цитата:
Цитата:
P.S. Наверное я привлек слишком много внимания, оказалось все так просто. Наверное слишком засиделся над одной темой. Надеюсь доделаю эту программу и она будет популярна и принесет пользу .. пользователям. А пока анонсов до релиза не делаю. Всем еще раз спасибо.
Пишу на чистом С, плюсы спилил.
Последний раз редактировалось LynXzp; 05.12.2012 в 22:47. |
||||||
05.12.2012, 23:03 | #16 | ||
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Поясняю
Цитата:
Цитата:
Если для каждой записи выделить фикс. массив указателей на свойства (или пар указатели-значения), то вы можете быстро (делением на 2) узнать, есть ли данное свойство у записи или нет. (если пары - то и его значение).
Благими намерениями устлана дорога на programmersforum.ru
|
||
05.12.2012, 23:12 | #17 |
Старожил
Регистрация: 19.08.2009
Сообщений: 2,119
|
LynXzp
Но принципиально это не повысит производительность. 10к записей - это смешной размер для любой БД. лично ворочал объемом на порядок больше на sqlite - все летало. нсли все же на си - то ити примерно тем же путем. для каждого критерия создать свой индекс для быстрого поиска - это может быть хэш-таблица, или [R/B] Tree, неважно. при каждой вставке синхронизировать индексы... как-то так. в C++ уже есть готовенькое решение - библиотека Boost.MultiIndex - изумительная вещь. Но поскольку ты - тракторист (Сишник (((: ) придется изобретать самому.
А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery
|
06.12.2012, 01:00 | #18 | |
Пользователь
Регистрация: 04.10.2012
Сообщений: 95
|
Чувствую себя школьником случайно попавшим на научное совещание по квантовой физике. Это какай-то популярный прием? Можно ссылку/название?
// Я программирование только в школе учил. Книжки про алгоритмы просто "мозг выжигают", а на практике они почти не нужны. Но пока ужинал и смотрел BBC пришла идея. Что если хранить двумерный массив (конечно не массив) битов 10000х10000 (есть ли в соотв. записи соотв. характеристика). Это получается 12мб. Когда попадается условие с характеристикой, берем один столбец и сразу проверяем 4-х байтное значение. Есть ли там единица. (вероятность не более 20 из 10000 * 8 бит * 4 байта = 0,064. Скорее всего нет, тогда одним сравнением можно отсеять сразу 8*4=32 записи и не проверять их. Если же это число >0 уже искать все записи (или по байтам пройтись). А суть структуры записей такова что характеристики соседних записей чаще очень похожи. Т.е. распределение 1 и 0 в массиве будет не случайной, а сгруппированной что еще лучше. + Можно сжать массив этот с огромным коэффициентом. Правда при 100 тыс * 100 тыс. это уже более 1Гб в распакованном виде. Можно хранить для каждой характеристики свою часть отдельно чтобы не все распаковывать. Но это все слишком усложняет, думаю не нужно будет применять. // Буду закрывать другой баг, быстродействие проверю позже, теория довольно надежна, и нету UI для И/ИЛИ/НЕ пока только одно условие в запросе. Цитата:
Пишу на чистом С, плюсы спилил.
|
|
06.12.2012, 01:20 | #19 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
С матрицей это жесть... Да простая замена строковых элементов указателями (значений -числами) решает практически все проблемы.
А вот упорядочение их в записи открывает другие возможности - можно группировать не пересекающиеся ни по одному свойству - двоичный поиск сохранится и скорость возрастет.
Благими намерениями устлана дорога на programmersforum.ru
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов | vedro-compota | Общие вопросы по программированию, компьютерный форум | 34 | 09.12.2012 13:11 |
Алгоритм поиска | Sylar9 | Общие вопросы C/C++ | 0 | 03.04.2012 12:38 |
A* алгоритм поиска | Nicko_mt | Помощь студентам | 2 | 04.10.2011 02:24 |
алгоритм поиска | незнайка_на_земле | Помощь студентам | 4 | 08.03.2011 10:46 |
Алгоритм поиска!!!! | vit1990 | Помощь студентам | 14 | 29.01.2011 21:18 |