Перемешивание очень длинной последовательности

[Ar2emiS]

Всем привет!
Стоит задача случайно перемешать последовательность символов (алфавит известный и фиксированный) длинной около 70млн символов. Подскажите как это проще всего реализовать?

[Croessmah]

std::shuffle?

[Ar2emiS]

Необходимо на языке Си.

[Serge_Bliznykov]

Сообщение от Ar2emiS

Стоит задача случайно перемешать последовательность символов (алфавит известный и фиксированный) длинной около 70млн символов.

простите, а при чём здесь алфавит?

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

перемешать можно по алгоритму отсюда

[Arigato]

По коду из ссылки:

 for i:=1 to N-1 do
  begin
   k:= Random(N-i+1)+i; // (1)
   if k<>i then begin // (2)
     buf:=mas[i];
     mas[i]:=mas[k];
     mas[k]:=buf;
   end;
  end;

Вычисление индекса (1) из оставшихся что дает в плане оптимизации или качестве перемешивания? Почему не считать индекс как Random(N) + 1, ну и цикл сделать до N?
Для 70 млн нет необходимости в проверке (2).

[Serge_Bliznykov]

Сообщение от Arigato

Вычисление индекса (1) из оставшихся что дает в плане оптимизации или качестве перемешивания?

Так это сделано для того, чтобы распределение перемешанных объектов было нормальное.

читайте статью:

Как не надо тасовать карты


Частичный перевод статьи
How We Learned to Cheat at Online Poker: A Study in Software Security
by Brad Arkin, Frank Hill, Scott Marks, Matt Schmid and Thomas John Walls

...введение пропущено... Авторы объясняют, что проанализировали программное обеспечение одного онлайн-казино.
Риски программного обеспечения
Тасование виртуальной колоды карт

например, ТУТ


ну и, насколько я понимаю, это просто реализация
алгоритма Тасование Фишера — Йетса (см. википедию)

[Arigato]

Serge_Bliznykov, понятно. Только там получается перевернутый вариант алгоритма, хотя суть та же. Набросал пример на Си, реализующий алгоритм тасование Фишера-Йетса:

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>

int main(){
	const int n=100;
	int mas[n];
	
	srand(time(NULL));
		
	for(int i=0; i<n; i++)
		mas[i] = i;
		
	for(int i=n-1; i>0; i--){
		int k=rand()%(i+1);
		int tmp=mas[i];
		mas[i]=mas[k];
		mas[k]=tmp;
	}
		
	for(int i=0; i<n; i++)
		printf("%d ", mas[i]);
	
	getch();
	return 0;
}

Но стоит отметить, что в чистом Си rand() дает случайное число 0..32767, то есть для 70 млн неприменим.

[Serge_Bliznykov]

Сообщение от Arigato

Набросал пример на Си, реализующий алгоритм тасование Фишера-Йетса

спасибо.

Сообщение от Arigato

Но стоит отметить, что в чистом Си rand() дает случайное число 0..32767, то есть для 70 млн неприменим.

да, это на самом деле большая проблема для реализации!
а как можно в чистом си получить случайное вещественное число от 0 до 1 ? (с нормальным распределением псч, разумеется)

а в данном случае, может быть, стоит так?

int64 bigRandom(){
   return rand()*rand();
}

[Arigato]

Нужно равномерное распределение. Можно вот так вычислить большое случайное число:

// Случайное число от 0 до 1 млрд
long lrand(long max){
	long rnd=
		1000000*(rand()%1000)+ // миллионы
		1000*(rand()%1000)+ // тысячи
		rand()%1000; // единицы
	return rnd%max;
}

int main(){
	srand(time(NULL));
	
	for(int i=0; i<100; i++)
		printf("%d\n", lrand(70000000));
	
	getch();
	return 0;
}

Какое будет у него распределение - не знаю.

return rand()*rand();

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

[Ar2emiS]

Последовательность хранится в файле. Хотелось бы не запихивать всю последовательность в массив, если способ это реализовать?
Поскольку 70млн - это еще не предел, в дальнейшем они будут в разы, а то еще и на порядок длиннее.
Или всё-таки самый простой и быстрый способ - это присвоить все массиву и его перемешивать?