ищет эффективную структуру данных для быстрого поиска

Question

У меня есть список элементов около 1000. Каждый элемент (объекты, которые я читаю из файла, следовательно, я могу эффективно расположить их в начале), содержит 4 переменные. Так что теперь я делаю следующее, что очень неэффективно при большой схеме вещей:

void func(double value1, double value2, double value3)
{

       fooArr[1000];

       for(int i=0;i<1000; ++i) 
       {
                   //they are all numeric! ranges are < 1000
                  if(fooArr[i].a== value1
                       && fooArr[i].b >= value2;
                       && fooArr[i].c <= value2; //yes again value2  
                       && fooArr[i].d <= value3; 
                   )
                   {
                            /* yay found now do something!*/
                    }
       } 
}

Пространство не так уж важно!

ИЗМЕНЕНО по ЗАПРОСУ

Answer 1

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

Сказав это, возможно, одна из возможностей - это сгенерировать несколько индексов. Основным индексом может быть словарь с ключом для свойства a, связывающий его со списком элементов с одинаковым значением для этого свойства. Если предположить, что значения этого свойства хорошо распределены, это немедленно исключит подавляющее большинство сравнений.

Если свойство имеет ограниченное количество значений, то вы можете рассмотреть возможность добавления дополнительного индекса, который сортирует элементы по b, а может быть даже другого, который сортирует по c (но в обратном порядке).