Хранение корзины чисел в эффективной структуре данных

Question

У меня есть наборы чисел, например - от 1 до 4, от 5 до 15, от 16 до 21, от 22 до 34, .... У меня примерно 600 000 таких ведер. Диапазон чисел, попадающих в каждое ведро, варьируется. Мне нужно хранить эти сегменты в подходящей структуре данных, чтобы поиск числа выполнялся как можно быстрее.

Итак, мой вопрос: какова подходящая структура данных и механизм сортировки для этого типа проблемы?

Заранее спасибо

Answer 1

Если сегменты являются смежными и непересекающимися, как в вашем примере, вам нужно хранить в векторе только левую границу каждого сегмента (то есть 1, 5, 16, 22) плюс, как последний элемент, первое число это не попадает ни в одно ведро (35). (Я предполагаю, конечно, что вы говорите о целых числах.)

Сохранить вектор отсортированным. Вы можете искать сегмент в O (log n) с помощью своего рода двоичного поиска. Чтобы найти, к какому сегменту относится число x, просто выберите единственный индекс i, такой что vector [i] <= x <vector [i + 1]. Если x строго меньше, чем vector [0], или если он больше или равен последнему элементу вектора, то ни один сегмент не содержит его. </p>

EDIT. Вот что я имею в виду:

#include <stdio.h>

// ~ Binary search. Should be O(log n)
int findBucket(int aNumber, int *leftBounds, int left, int right)
{
    int middle;

    if(aNumber < leftBounds[left] || leftBounds[right] <= aNumber) // cannot find
        return -1;
    if(left + 1 == right) // found
        return left;

    middle = left + (right - left)/2;

    if( leftBounds[left] <= aNumber && aNumber < leftBounds[middle] )
        return findBucket(aNumber, leftBounds, left, middle);
    else
        return findBucket(aNumber, leftBounds, middle, right);
}


#define NBUCKETS 12
int main(void)
{
    int leftBounds[NBUCKETS+1] = {1, 4, 7, 15, 32, 36, 44, 55, 67, 68, 79, 99, 101};
    // The buckets are 1-3, 4-6, 7-14, 15-31, ...

    int aNumber;
    for(aNumber = -3; aNumber < 103; aNumber++)
    {
        int index = findBucket(aNumber, leftBounds, 0, NBUCKETS);
        if(index < 0)
            printf("%d: Bucket not found\n", aNumber);
        else
            printf("%d belongs to the bucket %d-%d\n", aNumber, leftBounds[index], leftBounds[index+1]-1);
    }   
    return 0;
}

Answer 2

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

Предполагая, что ни один из диапазонов сегментов не перекрывается, я думаю, вы могли бы реализовать это в бинарном дереве поиска. Это сделало бы поиск возможным в O (logn) (когда n = количество сегментов).

Было бы просто сделать это, просто определите левую ветвь, чтобы она была меньше нижнего конца сегмента, а правая ветвь - больше, чем правый конец. Итак, в вашем примере мы получили бы дерево что-то вроде:

    16-21
    /    \
  5-15  22-34
  /
1-4

Чтобы найти, скажем, 7, вы просто проверяете root. Меньше 16? Да, иди налево. Меньше 5? Нет больше 15? Нет, все готово.

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

Answer 3

Возможно, вам понадобится какое-то сортированное дерево, например, B-Tree, B + Tree или Binary Search.

Answer 4

Дайте мне посмотреть, смогу ли я переформулировать ваше требование. Это похоже на наличие, скажем, дня года и желание знать, в каком месяце выпадает данный день? Итак, учитывая год с 600 000 дней (интересная планета), вы хотите вернуть строку «Jan», «Feb», «Mar» ... «Dec»?

Позвольте мне сначала сосредоточиться на конце поиска, и я думаю, что вы можете выяснить, как упорядочить данные при инициализации структур данных, учитывая то, что уже было опубликовано выше.

Создать структуру данных ...

typedef struct {
  int DayOfYear    :20; // an bit-int donating some bits for other uses
  int MonthSS      :4;  // subscript to select months
  int Unused       :8;  // can be used to make MonthSS 12 bits
} BUCKET_LIST;

  char MonthStr[12] = "Jan","Feb","Mar"... "Dec";
.

Чтобы инициализировать, используйте цикл for {}, чтобы установить BUCKET_LIST.MonthSS на один из 12 месяцев в MonthStr.

При получении выполните бинарный поиск по вектору BUCKET_LIST.DayOfYear (вам нужно написать тривиальную функцию сравнения для BUCKET_LIST.DayOfYear). Ваш результат может быть получен при использовании возврата из bsearch () в качестве индекса в MonthStr ...

pBucket = (BUCKET_LIST *)bsearch( v_bucket_list);
MonthString = MonthStr[pBucket->MonthSS];  

Общий подход здесь состоит в том, чтобы иметь наборы «указателей» на строки, прикрепленные к 600 000 записей. Все указатели в ведре указывают на одну и ту же строку. Я использовал бит int в качестве нижнего индекса здесь вместо 600k 4-байтовых указателей, потому что он занимает меньше памяти (4 бита против 4-х байтов), а BUCKET_LIST сортирует и ищет как разновидность int.

Используя эту схему, вы будете использовать не больше памяти или хранилища, чем для хранения простого ключа int, получить ту же производительность, что и простой ключ int, и покончить со всей проверкой диапазона при получении. IE : нет, если {} тестирование. Сохраните эти if {} для инициализации структуры данных BUCKET_LIST, а затем забудьте о них при извлечении.

Я называю этот метод псевдонимом индекса, так как он разрешает отношение многие-к-одному путем преобразования индекса многих в индекс одного индекса - очень эффективно, я мог бы добавить.

Мое приложение состояло в том, чтобы использовать массив из множества UCHAR, чтобы индексировать массив меньших чисел с плавающей точкой. Уменьшения размера было достаточно, чтобы сохранить все данные «горячей точки» в кэше L1 на процессоре. Увеличение производительности в 3 раза только из-за этого небольшого изменения.

Answer 5

+ 1 к виду бинарного поиска. Это просто и дает хорошую производительность для 600000 ведер. При этом, если это недостаточно, вы можете создать массив с элементами MAX BUCKET VALUE - MIN BUCKET VALUE = RANGE, и каждый элемент в этом массиве будет ссылаться на соответствующий сегмент. Затем вы получаете поиск в гарантированно постоянном [O (1)] времени за счет использования огромного объема памяти.

Если А) вероятность доступа к сегментам неравномерна и Б) вы знали / могли выяснить, насколько вероятно получить доступ к данному набору сегментов, вы, вероятно, могли бы объединить эти два подхода для создания своего рода кэша. Например, скажем, к контейнеру {0, 3} обращались все время, как и к {7, 13}, тогда вы можете создать массив CACHE. , .

int cache_low_value = 0;

int cache_hi_value = 13;

CACHE [0] = BUCKET_1

CACHE [1] = BUCKET_1

...

CACHE [6] = BUCKET_2

CACHE [7] = BUCKET_3

CACHE [8] = BUCKET_3

...

CACHE [13] = BUCKET_3

. , , что позволит вам найти интервал времени O (1), предполагая, что значение, которое вы пытаетесь связать с интервалом, находится между cache_low_value и cache_hi_value (если Y <= cache_hi_value && Y> = cache_low_value; тогда BUCKET = CACHE [ Y]). С другой стороны, этот подход не будет использовать всю память на вашем компьютере; с другой стороны, это добавило бы эквивалент дополнительной операции или двух к вашему bsearch в случае, если вы не можете найти свою пару число / сегмент в кэше (так как вам пришлось проверять кэш в первую очередь).

Answer 6

Простой способ хранить и сортировать их в C ++ - это использовать пару отсортированных массивов, которые представляют нижнюю и верхнюю границы каждого сегмента. Затем вы можете использовать int bucket_index= std::distance(lower_bounds.begin(), std::lower_bound(lower_bounds, value)), чтобы найти интервал, с которым будет совпадать значение, а if (upper_bounds[bucket_index]>=value), bucket_index - тот интервал, который вам нужен.

Вы можете заменить это одной структурой, содержащей ведро, но принцип будет таким же.