Я хочу, чтобы уникальный массив n элементов.уникальная крупномасштабная матрица/последовательность
n может быть до 10^9 и даже 10^11.
То есть, элементы могут не помещаться в памяти. Таким образом, наивный вид и уникальный подход ниже не будет работать (слишком медленно: сортировать и уникально, массив 10^8 занимает полминуты по одной теме).
sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());
К счастью, есть что-то поможет разработать алгоритм:
элементы подходят в 64-разрядное беззнаковое целое число (uint64_t). Поскольку элементы генерируются хэш-функцией, поэтому мы можем считать, что удовлетворяет равномерному распределению (~ U (0, 2^64-1)).
У меня есть кластер из не менее 10 многоядерных компьютеров/узлов, поэтому алгоритм может (и должен) быть разработан распределенным. И я имею право запускать код MPI C++. (Однако кластер не принадлежит мне самому, иногда могут быть другие программы, конкурирующие за процессорное время на любом компьютере/узле. Таким образом, задачи лучше отправляются на каждый компьютер/узел динамически)
Каждый компьютер/узлы имеют не менее 8 ядер, не менее 64 ГБ основной памяти и не менее 100 ГБ свободного пространства SSD. Кроме того, они подключаются через Gigabit Ethernet.
Может ли кто-нибудь помочь дать какое-либо предложение по разработке алгоритма? Этот подход требует много времени. Я хочу получить результат через час в кластере.
Are там много дублей руды они довольно редки? – MrSmith42
Вы можете попробовать std :: set? –
Я не уверен: «Много ли дубликатов или они довольно редки?» Без экспериментального результата. Я мог только предположить, что ** удовлетворяет равномерному распределению **. – buaagg