Задача выборки по критериям

Что дается на входе и что должно быть на выходе? Напиши сигнатуру желаемой функции.

Предполгагаем что имена полей следущие: a, b, c, d. Прототип функции: filter (85, [50000, 70000], 180, 70) На выходе должен быть массив или id обьектов или сами обекты.

Еще что-то?

База данных + индекс по каждому полю

Зачем тебе хеш, если требуется диапазоны? Тут твоя ошибка.

У тебя 4-ре ключа, для каждого строй дерево. Заведи числовой ID для каждой записи. Добейся что бы по запросу Fi(min,max) (i=1..4) выдавался отсортированный список ID записей, у которых i-ое поле в заданном диапазоне. Пересечение 4-х отсортированных списков, даст тебе нужный набор записей.

Я именно так и делаю. Но для диапозонов запрос выполняется под 10 сек. А если указатьв се поля лиапозонами, причем большими, за 10минут не завершился процесс.

Hash - это название Массива из руби. Из питона - Dict.

Тебе тут нужно своё дерево для хранения значений полей.

Решение нужно в обход БД. Нужно сделать чисто на ЯП. Без сторонних вещей

Смотри, примерно по первому полю которое от 0-100. У меня ассоциативный массив, у которого ключи 0-100. Содержимое ключа 1 => [4,7,9,10,20,24.....10 000 000] У каждого поля примерно по 100, 1000000, 200, 200 записей соответсвенно. Тоесть, когда у меня запрос идет прямыми значениями, я делаю примерно следующее:

a[85] & b[60000] & c[180] & d[70]

И на выходе получаю массив, обычно не больше 1к элементов. Отрабатывает меньше чем за 100мс. Момент следующий, когда у меня диапозон, я делаю следующее (в упрощенном варианте):

a[85] & (b[50000] | b[50001] | b[50002] ... b[59999] | b[60000]) & c[180] & d[70]

Беда в том, что второе поле от 0 и до 1 ляма, и диапозоны могут выдавать огромные массивы. Все эти операции очень затратны по времени. Я не уверен что смогу сильно сэкономить, если заменю ассоциативный массив(Ruby Hash) на дерево поиска, или любое другое. Вытаскивание списка id обьектов удовлетворяющих одному условию - это не медленная задача. Задача Провернуть пересечение с обьединением на массивах содержаших миллионы значений - вот в чем моя текущая проблема.

Если строить дерево(можно хеш - не суть важно), то как его делать для нескольких ключей сразу? Если посчитать все возможные варианты для 4х полей 100*1000000*200*200 = 4e12. Т.е. 4триллиона возможных комбинаций. Но, так как обьектов всего 10миллионов, могут быть как повторяющиеся, так и не быть комбинаций вообще.

PS

& - пересечение массивов

| - обьединение массивов

Сейчас только заметил, что у тебя маленькие диапазоны значений у полей. Используй для хранения списков ключей честные массивы (например, ndarray для Python), тогда время доступа к списку будет O(1).

Следующая задача - быстрое объединение списков. http://habrahabr.ru/post/63539/. Получишь 4-ре штуки

Далее ищи пересечение двух списков, но только правильно, а не через Ж*** как большинство решений в интернете

Иногда структуры с вертикальной иерархией вверху и горизонатально внизу (если можно так выразиться) бывают полезны. Что-то вроде unrolled linked list / rope / etc. Для второго индекса можно попробовать кучу, с литьями из 4к элементов.

Посмотрел я тут, что по времени выполнения/потребления памяти получается. Это только на Си переписывать и выдавать интерфейсы для Python/Ruby.

В питоне ndarray и тот не спасает.

Именно. Я даже посчитал, если правильную структуру сварганить, то на 10лямов обьектов будет примерно 100мб потребление памяти, без индексов. А в рубях у меня под 3гига в среднем, что не кисло.