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

[LynXzp]

1. Я так понял нет разделов "просто алгоритмы" без привязки к языку? (в принципе пишу на С, поэтому вопрос сюда)
2. Сама задача.
Есть много (~10 000) записей (структур). У каждой есть до 20 (почти всегда 20) характеристик в виде текст+число.
К примеру:
Слон - большой:100, нос:90, хвост:10, громкость:20, ухи:100.
Праздник - громкость:100, большой:80, детей:60, крови:1.

Количество разных текстовых характеристик (~10 000), их числовые значения колебаются от 0 до 100 включительно.

Возникают задачи выбрать из записей:
1) N самых больших.
2) N самых хвостатых и людей.
3) N самых громких или кровавых, но не детей.
И нужно выполнять задачи поиска менее чем за 1 секунду.

Задача 1-го типа если достаточно записей с такой характеристикой и числовым значением в 100 выполняется примерно секунду - уже критическое число. Если недостаточно 100, то (уменьшаю порог до 90 и прогоняю цикл поиска заново... пока не получу N записей) и уже не вкладываюсь.

Первая идея: предварительно в фоне просчитать чего-нить чтобы можно было бы это использовать в будущем (нет ограничений на время, но в разумных пределах). Но отсортированные записи по КАЖДОЙ характеристике слишком много. (Все записи весят 1Мб (примерно, без изб. инф.)) 1Мб*10 000 (facepalm)

Вторая идея - отсортировать в каждой записи все характеристики по возрастанию. Догадался только что, еще не сделал. Теоретически это ускорит решение задачи 1-го типа не более чем в 20 раз. 3-й тип ("не") менее чем в 2 раза - выходит за критический предел.

Может у кого появятся какие иные идеи?

[Rififi]

LynXzp

Есть много (~10 000) записей (структур). У каждой есть до 20 (почти всегда 20) характеристик в виде текст+число.

Возникают задачи выбрать из записей:
1) N самых больших.
2) N самых хвостатых и людей.
3) N самых громких или кровавых, но не детей.

На фига тут Си? В базу всё это и sql.

[LynXzp]

Это десктопное приложение.
Думал использовать sqlite
Но принципиально это не повысит производительность.

[MihalNik]

В любом случае быстрый поиск только если данные упорядочены, поэтому поддержка дополнительных структур. Если действительно только эти три запроса, то здесь 4 упорядоченных структуры с указателями на соответствующие записи. Во вторую включаются только люди, в 3 и 4 не вкл. дети. Упорядочение индексированием дает 4х101 динамических списка без особых заморочек

[LynXzp]

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

[Abstraction]

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

Не должно быть там секунды.

[MihalNik]

Как у Abstraction должно уложиться во время

[Smogg]

1 Мб на запись, в записи - двадцать характеристик. 20 чисел не больше 100 - это 20 байт. След., все - текст. Получается, самый времязатрат - поиск точного соответствия характеристики по названию. Тогда в чем смысл хранить столько дублирующей информации в каждой записи?
//примерно так я понимаю объяснение первого пункта предпоследнего перед моим комментария.

[MihalNik]

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

[Abstraction]

А, ещё:

2) N самых хвостатых и людей.

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

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