Какую структуру данных использовать?(хэш-карта против Trie против?)

Question

У меня есть функция C, которая производит около 6 миллионов уникальных массивов.Эти массивы всегда имеют 17 элементов каждый, и каждый элемент представляет собой целое число от 0 до 16. У меня также есть слегка модифицированная версия этой функции, которая также будет генерировать около 6 миллионов уникальных массивов одного типа.Моя проблема в том, что второй дает примерно на 45 000 результатов меньше, чем первый, и я хотел бы посмотреть, что это за результаты.

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

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

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

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

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

Answer 1

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

Целое число [0,16] может быть представлено в виде пятибитного числа, поэтому семнадцать из них могут быть представлены в виде 85-битной (11-байтовой) двоичной строки. Таким образом, вы можете просто использовать одну из множества доступных библиотек для хранения отсортированных / хэшированных наборов строк с проверкой членства на них, и все будет готово. Он не будет таким же быстрым или согласованным с кэшем, как настроенный файл, но он будет достаточно хорош, чтобы за несколько секунд перебрать 66 МБ данных, и все будет готово к обеду.

Если нет такой библиотеки, удобной для использования, и вам нужно работать с нуля, я просто составил бы отсортированный список строк, а затем провел тесты членства с помощью бинарного поиска. Это работает примерно так: O ( n log n + m ( n log n )) = O (2 раза; mn log n ) например, квадратичное время как m & rarr; n. Если это выполняется как автономное задание один или два раза во время производства, это может быть достаточно; если вы собираетесь делать это чаще, чем раз в день, я бы беспокоился о локальности кэша и использовал бы три или B-дерево.

Answer 2

Я думаю, вам нужно взвесить значение, выполняя это в C, просто чтобы избежать связи.

Я бы выводил каждый массив из C построчно как разделенные пробелом целые числа.Затем загрузите его из файла, чтобы создать набор байтовых массивов, подобных этому (код F #):

let load file =
  System.IO.File.ReadAllLines file
  |> Array.Parallel.map (fun s -> s.Split[|' '|] |> Array.map (int >> byte))
  |> set

, а затем вычислите разницу между двумя файлами, как эта:

load "file1.txt" - load "file2.txt"

Вероятно, это займет несколько минут.

Answer 3

Проще говоря:

• Представляет каждую перестановку в виде массива из 17 байтов
• Сохранить весь меньший набор как массив из вышеперечисленных (17 * 6M <98MB) </li>
• Сортируйте его в лексикографическом порядке, чтобы ваш компаратор для qsort просто звонил memcmp(left, right, 17)
• Для каждого элемента из большего набора найдите его в отсортированном массиве, используя двоичный код (используйте тот же компаратор, что и раньше, на этот раз с bsearch).

Каждый из последних двух шагов будет выполнять что-то порядка 6M * log (6M) сравнений, что составляет около 138M. Что, вероятно, еще меньше времени, чем требуется для написания кода. Что не долго, так как все так просто: -)

Answer 4

@ Стив Джессоп Вы можете сделать последний шаг в линейном времени, сделав более умный поиск, удалив ненужные значения массива, в котором мы ищем:

Предположим, что размер А и м размер В,

int counter_A = 0;
int counter_B = 0;
int counter_C = 0;
while(counter_A != n){
    int temp = A[counter_A];
    counter_A++;
    //Removes all elements at the beginning of B since they are inferior than all
    //elements in A because they are inferior than the minimum of A
    for(;counter_B < m && B[counter_B] < temp;counter_B++);
    if((counter_B < m && B[counter_B] > temp) || counter_B == m){
        C[counter_C] = temp;
        counter_C++;
    }
}

Это должно выполняться за время O (n + m), поскольку каждый шаг алгоритма выполняет хотя бы одно увеличение счетчика.

Answer 5

Зависит от того, какой из них в вашем случае получит лучшую производительность памяти.А также, какую хеш-функцию вы используете, как разрешить коллизию и т. Д.

Answer 6

a) создайте структуру, которая содержит два 64-битных целых числа

b), поскольку каждый результат содержит 17 элементов, умножьте первые 8 и поместите результат в первое целое число, умножьте остальные 7 и поместитерезультат на втором int.

c) создать оператор <для вашей структуры </p>

d) создать набор вашей структуры и вставить все ваши результаты из первого запуска

e) переберите результаты второго запуска и выполните набор :: find ()

class Result
{
public:
    Result(int arr[17]);              // Fill-in _n1 and _n2

    bool operator < (const Result& r) const  // Compare
    { 
        if (_n1 != r._n1)
           return _n1 < r._n1;
        return _n2 < r._n2;
    }

protected:
    int _n1;
    int _n2;
};

typedef std::set< Result > SetResult;
SetResult setResult;

Edwin