Предложите хороший метод с наименьшим временем поиска - PullRequest
Новая
       22

Предложите хороший метод с наименьшим временем поиска

2 голосов
/ 12 апреля 2010

У меня есть структура, которая имеет 3 поля идентификатора и одно поле значения. У меня есть список этих объектов. Чтобы провести аналогию, поля идентификаторов похожи на первичные ключи объекта. Эти 3 поля однозначно идентифицируют объект. 

Class
{
   int a1;
   int a2;
   int a3;
   int value;
};

У меня был бы список, скажем, 1000 объектов этого типа данных. Мне нужно проверить конкретные значения этих значений ключей идентификации, передавая значения a1, a2 и a3 в функцию поиска, которая проверяет, присутствует ли какой-либо объект с этими конкретными значениями a1, a2 и a3, и возвращает это значение. Каков наиболее эффективный способ реализовать это для достижения наилучшего времени поиска?

Одним из решений, которое я мог бы придумать, было бы иметь трехмерную матрицу длины, скажем 1000, и заполнить ее значением. Это время поиска O (1). Но недостатки есть. 1. Мне нужно знать длину массива. 2. Для полей с более высокими единицами (скажем, 20) мне понадобится матрица из 20 измерений, которая будет излишним в памяти. Для моей фактической реализации у меня есть 23 поля идентичности.

Можете ли вы предложить хороший способ хранения этих данных, который дал бы мне лучшее время поиска?

Ответы [ 3 ]

4 голосов
/ 12 апреля 2010

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

0 голосов
/ 12 апреля 2010

Я бы просто отсортировал массив по ключу и использовал бинарный поиск.

(непроверенные) 

int compare_entry(ENTRY *k1, ENTRY *k2) {    
    int d = k1->a1 - k2->a1;
    if (d == 0) {
        d = k1->a2 - k2->a2;
        if (d == 0) {
            d = k1->a3 - k2->a3;
        }
    }
    return d; // >0 is k1 > k2, 0 if k1 == k2, <0 if k1 < k2
}

// Derived from Wikipedia
int find(ENTRY *list, int size, ENTRY *value) {
   int low = 0;
   int n = size - 1;
   int high = n;
   while (low < high) {
       int mid = low + (high - low) / 2
       int cmp = compare_entry(&list[mid], value);
       if (cmp < 0) {
           low = mid + 1;
       } else {
            high = mid; 
       }
   }
   if (low < n) {
       int cmp = compare_entry(&list[low], value);
       if (cmp == 0) {
           return low; // found item at 'low' index
       }
   } else {
        return -1;  // not found
   } 
}

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

если ваш a1-a3 находится в диапазоне 0-100, вы можете сделать свой ключ a1 * 10000 + a2 * 100 + a3 и выполнить одно сравнение, и наихудший случай - 63 целочисленных математических операции. И весь ваш массив помещается в кеш практически на любом современном процессоре. И это эффективная память.

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

0 голосов
/ 12 апреля 2010

Использовать хеш-таблицу (карту). Создайте ключ «a1-a2-a3» и сохраните данные в H (ключ) = data.

...