Что самый быстрый путь состоит в том, чтобы считать уникальными элементами в списке миллиарда элементов?

Если то, В чем Вы нуждаетесь, является близким приближением уникальных количеств, затем ищут алгоритм HyperLogLog . Это используется для получения близкой оценки кардинальности больших наборов данных как тот, к которому Вы обращаетесь. Google BigQuery, использование Reddit это в подобных целях. Много современных баз данных реализовали это. Это довольно быстро и может работать с минимальной памятью.

Если элементы являются строками, которые сопоставимы ... Тогда я бы предложил отказаться от идеи хешистого и идущего с чем-то, как двоичное поиск. Есть несколько реализаций в C # (никто не встроен в рамках). Обязательно получите тот, который сбалансирован, как красное черное дерево или дерево AVL.

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

Кроме того, поскольку он отсортирован, время поиска и введения - это оба журнал (n).

Вероятнее всего, вы запрашиваете недопустимый размер предварительного просмотра. Если вы проверите результаты adb logcat , вы, вероятно, увидите что-то подобное:

E/QualcommCameraHardware(22732): Invalid preview size requested: 480x724

Решение состоит в том, чтобы запросить ближайший доступный размер предварительного просмотра к желаемому; можно получить список доступных размеров предварительного просмотра, вызвав getSupportedPreviewSize в объекте Camera.Parameters , возвращаемом Camera.getParameters .

Пробовали ли вы хэш-карту (словарь в .Net)? Словарь < последовательность, байт > занимает только 5 байт на запись на x86 (4 для указателя на пул последовательностей, 1 для байта), что составляет около 400M элементов. Если дубликатов много, они должны уметь умещаться. С точки зрения реализации, это может быть неверно медленно (или не работать), так как также необходимо хранить все эти последовательности в памяти.

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

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

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

Проверьте Инструменты для автоматизированного тестирования графического интерфейса пользователя в окнах

Я использовал WebAii из ArtOfTest с хорошей степенью успеха в автоматизации интеграционного тестирования для приложения Silverlight.

Microsoft UI Automation, преемник Active Accessibility, может выполнять почти все необходимые функции автоматизации Windows UI.

С несколькими миллиардами последовательностей, даже если несколько процентов уникальны, шансы на хеш-коллизию довольно высоки (хеш-коды .NET имеют 32-битный int, что дает примерно 4 миллиарда уникальных хеш-значений. Если у вас всего 100 миллионов уникальных последовательностей, риск хеш-коллизии может быть недопустимо высоким). Статистика не моя самая сильная точка, но некоторые google исследования выясняют, что вероятность столкновения для идеально распределенного 32-битного хеша составляет (N - 1 )/2 ^ 32, где N - количество уникальных вещей, которые хэшируются.

Вы запускаете НАМНОГО меньшую вероятность хеш-коллизии, используя алгоритм, который использует значительно больше битов, , такой как SHA-1 .

Предполагая адекватный алгоритм хеширования, одним простым подходом, близким к тому, что вы уже пытались, было бы создание массива хеш-таблиц. Разбейте возможные хэш-значения на достаточно числовых диапазонов, чтобы ни один блок не превышал предел 2GB на объект. Выберите правильную хэш-таблицу на основе значения хэш-таблицы, затем выполните поиск в этой хэш-таблице. Например, можно создать 256 хэш-таблицы и использовать (HashValue)% 256 для получения номера хэш-таблицы от 0.. 255. Этот же алгоритм используется при назначении последовательности сегменту и при ее проверке/извлечении.

Я бы использовал базу данных, любая база данных будет делать.

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

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

Я согласен с другими плакатами относительно Решение базы данных, но дальше к этому, разумно-интеллектуальное использование триггеров и потенциально милая схема индексации (т. Е. Численное представление строк) будет самым быстрым подходом, ИМХО.

Разделить и завоевать - разбиение данные по первым 2 буквам (скажем,)

Словарь XX => Словарь строки => Подсчет

Я бы рассмотрел TRIE или направленный диаграмма ациклического слова , который должен быть более космически эффективным, чем хэш-таблица. Тестирование для членства строки будет o (len), где Len - это длина входной строки, которая, вероятно, такой же, как функция хеширования строки.

Вы пробовали хэш-карту (словарь в .NET)? Словарь займет 5 байтов за запись на x86 (4 для указателя на пул String, 1 для байта), который составляет около 400 м. Если есть много дубликатов, они должны быть в состоянии соответствовать. Реализация-мудрый, это может быть Verrryy Slow (или не работает), поскольку вам также нужно хранить все эти строки в памяти.

Если строки очень похожи, вы также можете написать свою реализацию TRIE .

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

Это может быть решено в худшем случае O ( N ), используя Sortix с счетным сортировкой в ​​качестве стабильного сорта для каждого положения символов. Это теоретически лучше, чем использование хеш-таблица (o ( n ), но не гарантировано) или mergeort (o ( n log n )). Использование TRIE также приведет к тому времени в худшем случае O ( N ) - время в ) (поиск постоянного времени через n клавиш n , поскольку все строки имеют ограниченную длину, которая является небольшой постоянной ), так что это сопоставимо. Я не уверен, как они сравнивают на практике. Radix Сортировка также довольно проста в реализации, и есть много существующих реализаций.

Если все строки d символов или короче, и количество различных символов k , затем Radix Sort принимает o ( d ( N + K )) Время для сортировки n клавиш. После сортировки вы можете пройти отсортированный список в O ( n ) времени и увеличивать счетчик каждый раз, когда вы попадаете в новую строку. Это будет количество различных строк. С d d составляет ~ 15 и k относительно малы по сравнению с N (миллиард), время работы не так уж плохо.

Это использует o ( DN ) пространство, хотя (для удержания каждой строки), поэтому он менее экономичен, чем попытки.

Словарь <> внутренне организован как список списков. Вы не приблизитесь к пределу (2 ГБ / 8) ^ 2 на 64-битной машине.

+1 Для решений SQL / DB сохраняет вещи простыми --will позволяет сосредоточиться на реальной задаче под рукой.

Но только для академических целей я хотел бы добавить мои 2 цента.

-1 для HASHTABLES. (Я не могу проголосовать еще). Поскольку они реализуются с использованием ведер, стоимость хранения может быть огромной во многих практических реализации. Кроме того, я согласен с Eric J, шансы на столкновения подрывают преимущества эффективности времени.

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

Пространство станет проблемой с сортировкой Radix или аналогичными реализациями (как упомянуты Kirarinsnow), потому что набор данных огромна.

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

Если у нас есть хранилище для проведения 1 миллиарда элементов в моей памяти, мы можем пойти на сортировку их на месте на уровне сортировку Heap в θ (n log n), а затем просто пройден Коллекция один раз в O (N) Время и выполнение этого:

if (a[i] == a[i+1])
    dupCount++;

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

Я хотел бы удержать от быстро-сортировки , потому что набор данных огромна. Если бы я мог сжать в некоторой памяти для второго случая, я бы лучше использовать его, чтобы уменьшить количество проходов, а не тратить его в сортировку слияния / быстро-сортировки (на самом деле, он сильно зависит от типа ввода, который мы имеем под рукой ).

Редактировать: решения SQL / DB хороши только при необходимости хранить эти данные в течение длительного времени.