Алгоритм поиска наиболее подходящих

[MihalNik]

"Запросы с любыми комбинациями И/ИЛИ/НЕ на любые характеристики (а их 10 000 для типичного пользователя)"
Т.е. чисто гипотетически в запросе м.б. тысячи логических условий

[Abstraction]

Т.е. чисто гипотетически в запросе м.б. тысячи логических условий

Вопрос в том, как предполагается поступать, если у объекта такой характеристики нет. То есть, возможно, на здоровых запросах получится сделать предварительный автомат-фильтр, способный быстро отсеивать элементы как заведомо непригодные.

[MihalNik]

и. Тогда определение того, есть ли у объекта некоторая характеристика, может быть организовано как линейный поиск

если использовать указатели на характеристики+байт значения то их можно упорядочить и юзать двоичный поиск

[LynXzp]

1) Свойства-тексты в отдельную таблицу, в объектах хранить только индекс свойства в таблице.

С самого начала думал так, забыл. :D

2) Составить массив указателей на объекты (10000 - немного).
3) При каждом запросе упорядочивать массив и выбирать первые N записей.

А это да, туплю вдвойне! Вместо того чтобы один раз посчитать и отсортировать. Каждый раз уменьшаю порог входимости и пересчитываю значения для всех. Вот здесь огромное спасибо! Должно работать быстро и при большем количестве (может быть и в 10 раз больше и, я б даже сказал в клинических случаях, в 100 раз больше, но в основном не более 10k*10k).

Записи были даны изначально, 1 мб - это очень мало записей-то (несколько тысяч, все там должно очень быстро работать.

1Мб это примерно. Файл весит более 3-х, но там еще другие данные.... Сейчас сам попытался посчитать 3Мб/10 000 = 300 байт - какие тут 10 000 записей... Есть конечно пустые, но даже и не думал что их столько. (Некоторые записи не содержат "характеристик").

В целом спасибо, особенно Abstraction. Не будет такого падения производительности как у меня сейчас при сложных условиях.

[LynXzp]

Сообщение от Abstraction

А, ещё:Как должно трактоваться такое условие?

не менее [не менее или точно - особенность реализации, не важно, лишь бы не менее, больше не страшно] N записей у которых обязательно есть и характеристика "хвост" и характеристика "людей". А самые определяются как суммарное значение числовых данных этих характеристик.

Сообщение от Abstraction

Точнее, можно ли построить автомат, который бы сопоставил каждому объекту некоторое целое число M так, что A "самее" B если и только если M(A)>M(B)? В этом случае имеет смысл делать массив пар (указатель на объект, оценка объекта) и сортировать его.

Ну ваше предыдущее сообщения в п.2 и п.3. именно так я и понял.
1. Создать массив указателей и числовых значений.
2. Заполнить эти числовые значения в соотв. с условием.
3. Отсортировать и выбрать наиболее подходящие.

Сообщение от Abstraction

P.S. Также может оказаться выгодным трюк держать в объекте массив из 21 "характеристики", забивая все лишние нулевыми значениями. Тогда определение того, есть ли у объекта некоторая характеристика, может быть организовано как линейный поиск, что на 20 элементов может оказаться быстрее алгоритма поиска в отсортированном массиве.

Честно говоря совсем не понял.

Сообщение от MihalNik

Т.е. чисто гипотетически в запросе м.б. тысячи логических условий

Ограничений я не ставил, хотя в принципе их нет, но они будут набиваться пользователем, редко когда будет больше 10, а чаще всего простая выборка по одной характеристике.

Сообщение от Abstraction

Вопрос в том, как предполагается поступать, если у объекта такой характеристики нет. То есть, возможно, на здоровых запросах получится сделать предварительный автомат-фильтр, способный быстро отсеивать элементы как заведомо непригодные.

Если требуемой характеристики нет, то запись не должна попасть в рез-т. Если числовое значение характеристики 0 - то считается что она есть, но значение минимально и попадет в рез-т только если не наберется необходимого кол-ва записей "лучше".

Сообщение от Abstraction

То есть, возможно, на здоровых запросах получится сделать предварительный автомат-фильтр, способный быстро отсеивать элементы как заведомо непригодные.

А если считать как по алгоритму из трех пунктов что в этом сообщении выше я составил с вашей помощью, то это и будет отсеивание, для одного запроса придется проходить 1 раз каждую запись.

P.S. Наверное я привлек слишком много внимания, оказалось все так просто. Наверное слишком засиделся над одной темой. Надеюсь доделаю эту программу и она будет популярна и принесет пользу .. пользователям. А пока анонсов до релиза не делаю. Всем еще раз спасибо.

[MihalNik]

Поясняю

Цитата:
Сообщение от Abstraction Посмотреть сообщение
P.S. Также может оказаться выгодным трюк держать в объекте массив из 21 "характеристики", забивая все лишние нулевыми значениями. Тогда определение того, есть ли у объекта некоторая характеристика, может быть организовано как линейный поиск, что на 20 элементов может оказаться быстрее алгоритма поиска в отсортированном массиве.
Честно говоря совсем не понял.

а также

если использовать указатели на характеристики+байт значения то их можно упорядочить и юзать двоичный поиск

У вас есть набор условий (т.е. усл1, усл2 и т.д.) вам нужно выбирать записи, причем по неск. критериям.
Если для каждой записи выделить фикс. массив указателей на свойства (или пар указатели-значения), то вы можете быстро (делением на 2) узнать, есть ли данное свойство у записи или нет. (если пары - то и его значение).

[Rififi]

LynXzp

Но принципиально это не повысит производительность.

10к записей - это смешной размер для любой БД.
лично ворочал объемом на порядок больше на sqlite - все летало.

нсли все же на си - то ити примерно тем же путем.
для каждого критерия создать свой индекс для быстрого поиска - это может быть хэш-таблица, или [R/B] Tree, неважно.
при каждой вставке синхронизировать индексы... как-то так.

в C++ уже есть готовенькое решение - библиотека Boost.MultiIndex - изумительная вещь. Но поскольку ты - тракторист (Сишник (((: ) придется изобретать самому.

[LynXzp]

Чувствую себя школьником случайно попавшим на научное совещание по квантовой физике. Это какай-то популярный прием? Можно ссылку/название?
// Я программирование только в школе учил. Книжки про алгоритмы просто "мозг выжигают", а на практике они почти не нужны.

Но пока ужинал и смотрел BBC пришла идея. Что если хранить двумерный массив (конечно не массив) битов 10000х10000 (есть ли в соотв. записи соотв. характеристика). Это получается 12мб. Когда попадается условие с характеристикой, берем один столбец и сразу проверяем 4-х байтное значение. Есть ли там единица. (вероятность не более 20 из 10000 * 8 бит * 4 байта = 0,064. Скорее всего нет, тогда одним сравнением можно отсеять сразу 8*4=32 записи и не проверять их. Если же это число >0 уже искать все записи (или по байтам пройтись). А суть структуры записей такова что характеристики соседних записей чаще очень похожи. Т.е. распределение 1 и 0 в массиве будет не случайной, а сгруппированной что еще лучше. + Можно сжать массив этот с огромным коэффициентом.

Правда при 100 тыс * 100 тыс. это уже более 1Гб в распакованном виде. Можно хранить для каждой характеристики свою часть отдельно чтобы не все распаковывать. Но это все слишком усложняет, думаю не нужно будет применять. // Буду закрывать другой баг, быстродействие проверю позже, теория довольно надежна, и нету UI для И/ИЛИ/НЕ пока только одно условие в запросе.

P.S. История. В универе попал в кружок по программированию. Дали задачи а на след. неделе рассказывали как правильно их решать. Одну из задач хотелось решить полным перебором, но ест-но ни в какое разумное время перебор не вкладывался. Больше пары рассказывали какую-то теорию с помощью которой можно решить эту задачу (в основном для тех кто учился на программистов, я смысл потерял еще в начале) а в конце писали код... сначала было много, потом уменьшился до довольно небольшого алгоритма. Я же пытался решить через полный перебор, но с ухищрениями - примерно как тут - отбрасывая ненужные циклы простым сравнением. (Получалось полный перебор + несколько условий между циклами.) В рез-те код оказался 1:1. (Правда я думал над ним чуть ли не неделю) Ляпнул что "не очень то и отличается от полного перебора", на что мне промыли мозг и понял я еще меньше. Там наверное думали что я хоть что-то понимал.

[MihalNik]

С матрицей это жесть... Да простая замена строковых элементов указателями (значений -числами) решает практически все проблемы.
А вот упорядочение их в записи открывает другие возможности - можно группировать не пересекающиеся ни по одному свойству - двоичный поиск сохранится и скорость возрастет.