Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.09.2017, 18:12   #1
Ar2emiS
Пользователь
 
Регистрация: 18.10.2016
Сообщений: 27
По умолчанию Перемешивание очень длинной последовательности

Всем привет!
Стоит задача случайно перемешать последовательность символов (алфавит известный и фиксированный) длинной около 70млн символов. Подскажите как это проще всего реализовать?
Ar2emiS вне форума Ответить с цитированием
Старый 03.09.2017, 19:04   #2
Croessmah
Вредный кошак
Участник клуба
 
Аватар для Croessmah
 
Регистрация: 14.10.2012
Сообщений: 1,159
По умолчанию

std::shuffle?
Croessmah вне форума Ответить с цитированием
Старый 03.09.2017, 20:35   #3
Ar2emiS
Пользователь
 
Регистрация: 18.10.2016
Сообщений: 27
По умолчанию

Необходимо на языке Си.
Ar2emiS вне форума Ответить с цитированием
Старый 04.09.2017, 10:08   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Ar2emiS Посмотреть сообщение
Стоит задача случайно перемешать последовательность символов (алфавит известный и фиксированный) длинной около 70млн символов.
простите, а при чём здесь алфавит?

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

перемешать можно по алгоритму отсюда
Serge_Bliznykov вне форума Ответить с цитированием
Старый 04.09.2017, 10:55   #5
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

По коду из ссылки:
Код:
 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).
Arigato на форуме Ответить с цитированием
Старый 04.09.2017, 11:05   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от 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

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


ну и, насколько я понимаю, это просто реализация
алгоритма Тасование Фишера — Йетса (см. википедию)
Serge_Bliznykov вне форума Ответить с цитированием
Старый 04.09.2017, 12:08   #7
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

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 млн неприменим.

Последний раз редактировалось Arigato; 04.09.2017 в 12:12.
Arigato на форуме Ответить с цитированием
Старый 04.09.2017, 13:12   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

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

Цитата:
Сообщение от Arigato Посмотреть сообщение
Но стоит отметить, что в чистом Си rand() дает случайное число 0..32767, то есть для 70 млн неприменим.
да, это на самом деле большая проблема для реализации!
а как можно в чистом си получить случайное вещественное число от 0 до 1 ? (с нормальным распределением псч, разумеется)

а в данном случае, может быть, стоит так?
Код:
int64 bigRandom(){
   return rand()*rand();
}

Последний раз редактировалось Serge_Bliznykov; 04.09.2017 в 13:16.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 04.09.2017, 14:18   #9
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

Нужно равномерное распределение. Можно вот так вычислить большое случайное число:
Код:
// Случайное число от 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();
Как минимум контрпример: если ноль выпадает в левой или в правой части, в произведении получаем ноль. То есть вероятность нуля выше любого другого значения.

Последний раз редактировалось Arigato; 04.09.2017 в 14:22.
Arigato на форуме Ответить с цитированием
Старый 04.09.2017, 19:34   #10
Ar2emiS
Пользователь
 
Регистрация: 18.10.2016
Сообщений: 27
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение самой длинной последовательности ARV.net C# (си шарп) 7 03.11.2012 13:06
Перемешивание массива revaldo666 Общие вопросы C/C++ 6 19.01.2011 15:04
Перемешивание строк gamer123 Общие вопросы Delphi 17 25.08.2010 20:10
Текст в очень длинной таблице ANG3 Microsoft Office Word 2 27.01.2010 19:58
Перемешивание строк Черничный БД в Delphi 3 15.07.2008 14:11