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

Question

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

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

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

Answer 1

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

Держите вектором отсортированным. Вы можете искать ведро в O (log n), с видом двоичного поиска. Для поиска, к какому ведру принадлежат номер X, просто идут на единственный индекс, который я такой, который Vector [I] <= X <Vector [I + 1]. Если X строго меньше, чем вектор [0], или если оно больше или равно последним элементе вектора, то не содержит его ведро.

РЕДАКТИРОВАТЬ. Вот что я имею в виду:

#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

Вы, вероятно, захотите какое-то сортированное дерево, как B-дерево, дерево B + или двоичное дерево поиска.

Answer 3

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

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

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

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

Для поиска, скажем, 7, вы просто проверяете корень. Менее 16? Да, иди налево. Менее 5? Нет 15? Нет, ты закончил.

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

Answer 4

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

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

Answer 5

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

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

int cache_low_value = 0;

int cache_hi_value = 13;

Кэш [0] = Bucket_1

Кэш [1] = Bucket_1

...

Кэш [6] = Bucket_2

Кэш [7] = Bucket_3

Кэш [8] = Bucket_3

...

Кэш [13] = Bucket_3

. Отказ Отказ Отказ Что позволит вам найти ведро в O (1) время, предполагая, что значение, которое вы пытаетесь связать значение с ведром, между CACHE_LOW_VALUE и CACHE_HI_VALUE (если y <= cache_hi_value && y> = cache_low_value; затем bucket = cache У]). На стороне этот подход не будет использовать всю память на вашем компьютере; В нижней стороне, это добавило эквивалент дополнительной работы или два в ваш BSearch в том случае, вы не можете найти вашу пару номера / ведра в кэше (поскольку вам нужно было проверить кеш в первую очередь).

Answer 6

Позвольте мне посмотреть, смогу ли я передумать ваши требования. Это аналогично, скажем, день года, и желая узнать, в каком месяце в день входит день? Итак, учитывая год с 600 000 дней (интересная планета), вы хотите вернуть строку, которая является либо «Ян», «Фев», «Мар» ... «дек»?

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

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

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";
.

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

На извлечение, провести двоичный поиск по вектору Bucket_List.dayofyear (вам нужно будет написать функцию тривиального сравнения для Bucket_List.dayofyear). Ваш результат можно получить, используя возврат от BSEARCH () в качестве индекса на Monsestr ...

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

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

Используя эту схему, вы не будете использовать больше памяти или хранения, чем хранение простой клавиши Int, получите то же самое, что и простой ключ int, И покончить со всей проверкой диапазона на поиск. Т.е. нет, если {} тестирование. Сохраните те, если {} s для инициализации структуры данных Bucket_List, а затем забыть о них по поиску.

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

Мое приложение было использовать массив многих UCHARS, чтобы индексировать гораздо меньший массив двойных поплавок. Снижение размера было достаточно, чтобы сохранить все данные горячего места в кэше L1 на процессоре. 3X Выполнение производительности только от этого мало изменений.