Модераторы: korob2001, ginnie
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> случайно поменять местами N% символов в строке, наиболее оптимальный алгоритм 
:(
    Опции темы
Ramirez
Дата 3.9.2007, 14:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5



Необходимо случайным образом переставить местами N% символов в строке. Как наиболее оптимально это сделать?
У меня только какие-то страшные нагромождения получаются =(

Это сообщение отредактировал(а) Ramirez - 3.9.2007, 15:08
PM ICQ   Вверх
tishaishii
Дата 3.9.2007, 15:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



Код
sub randomize {
    my($len, $str, $res)=(length $_[0], shift);
    $res.=substr $str, rand $len--, 1, undef while $len;
    +$res
}

print randomize abcdefghijklmnopqrstuvwxyz


Добавлено через 7 минут и 19 секунд
Код
sub randomize {
    my($len, $str, $i, $res)=(length $_[0], shift);
    substr($res, rand $i++, 0)=substr $str, $len--, 1, undef while $len;
    +$res
}

print randomize abcdefghijklmnopqrstuvwxyz


Добавлено через 10 минут и 21 секунду
А здесь настраиваемый беспорядок.
Второй параметр не должен быть больше длинны строки.
Код
sub randomize {
    my($len, $str, $shuffle)=(length $_[0], \shift, shift);
    $shuffle%=$len;
    substr($$str, rand $len, 0)=substr $$str, rand $len--, 1, undef while $shuffle--;
    +$str
}

print ${+randomize abcdefghijklmnopqrstuvwxyz, 10};


Это сообщение отредактировал(а) tishaishii - 3.9.2007, 15:38
PM MAIL ICQ Skype   Вверх
Ramirez
Дата 3.9.2007, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5



спасибо, фен-шуй, блин =) 
только эта функция вообще все перемешивает, а мне надо было перемешивать некоторый процент символов.

Это сообщение отредактировал(а) Ramirez - 3.9.2007, 15:48
PM ICQ   Вверх
tishaishii
Дата 3.9.2007, 15:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



Последняя?
Перемешивает и настраивается сколько символов перемешивать.

Ну из последней легко сделать это:
Код
sub randomize {
    my($len, $shuffle, $str)=(length $_[0], int $_[1] * length $_[0], \shift);
    substr($$str, rand $len--, 0)=substr $$str, rand $len, 1, undef while $shuffle--;
    +$str
}

print ${
    +randomize abcdefghijklmnopqrstuvwxyz, 2#00%
};


Это сообщение отредактировал(а) tishaishii - 3.9.2007, 15:59
PM MAIL ICQ Skype   Вверх
Ramirez
Дата 3.9.2007, 15:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5



погоди. хорошо тебе, со встроенным оптимизатором кода, а мне надо сначала переварить как оно работает =)
PM ICQ   Вверх
tishaishii
Дата 3.9.2007, 16:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



Цитата
хорошо тебе, со встроенным оптимизатором кода

smile)) Инсталлировал его не долго. Тихими тёплыми ночами с заданиями.
К стати, где взять такой оптимизатор?
PM MAIL ICQ Skype   Вверх
amg
Дата 4.9.2007, 08:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50



tishaishii, твой последний алгоритм затрагивает начало строки с гораздо больней вероятностью, чем конец, и переставляет уже однажды переставленные символы. Например, твой
randomize($str, 1) может дать THCOJfGDAKIElVmnBpqrsuwxyz (заглавные буквы - переставленные),
хотя по условию задания нужно было "переставить местами 100% символов в строке". Но, может быть, я неправильно понял задание.

Другой вариант, со вспомогательным массивом:
Код

$str = 'abcdefghijklmnopqrstuvwxyz';
print randomize($str, 0.1), "\n";

sub randomize {
  my @str = split '', $_[0];
  my $shuffle = int($_[1] * @str / 2);
  my @a = 0..$#str;
  while ($shuffle--) {
    my ($place1, $place2) = (splice(@a,rand @a,1), splice(@a,rand @a,1));
    # uc в следующей строке - для наглядности, из рабочего кода убрать
    ($str[$place1], $str[$place2]) = (uc $str[$place2], uc $str[$place1]);
  }
  return join '', @str;
}


PM MAIL   Вверх
tishaishii
Дата 5.9.2007, 17:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



Ну это только за счёт $len--. А если текст большой? Как работать с массивом символов и указателями?

Вот без $len--. А значит, всё зависит от псевдо-случайной величины: переставить $shuffle раз любой символ с любым. Чтобы переставить строго N% символов - недо ещё морочаться, тогда задача может быть гораздо сложнее. Вот простое решение как переставить <=N% символов.
Код
sub randomize {
    my($len, $shuffle, $str)=(length $_[0], int $_[1] * length $_[0], \shift);
    substr $$str, rand $len, 0, substr $$str, rand $len, 1, undef while $shuffle--;
    +$str
}

print ${
    +randomize abcdefghijklmnopqrstuvwxyz, 2#00%
}



Это сообщение отредактировал(а) tishaishii - 5.9.2007, 18:06
PM MAIL ICQ Skype   Вверх
tishaishii
Дата 5.9.2007, 18:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



В результате 1_000_000 испытаний с указанными 20% перестановок букв в тексте, число букв хотя бы один раз переставленных, сводится к 23.076923077267%????. При чём, как оказалось, это число не зависит от количества заявленных процентов букв для смешивания (второй аргумент). ????

Код

sub randomize {
    my($len, $shuffle, $str)=(length($_[0]), int($_[1] * length $_[0]), \shift);
    substr $$str, rand $len, 0, uc substr $$str, rand $len, 1, undef while $shuffle--;
    +$str
}

my$str='abcdefghijklmnopqrstuvwxyz';
my$len=length $str;
my$summ=0;
my$res;

for(my$i=0; $i<1e6; $i++) {
    $res=&randomize($str, .2);
    $summ+=int($res=~tr{ABCDEFGHIJKLMNOPQRSTUVWXYZ}{ABCDEFGHIJKLMNOPQRSTUVWXYZ})/$len;
}

print $summ/1e6;


Задача: алгоритм, который гарантировал бы перестановку =N% символов.

Это сообщение отредактировал(а) tishaishii - 5.9.2007, 18:12
PM MAIL ICQ Skype   Вверх
amg
Дата 6.9.2007, 08:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50



Цитата(tishaishii @  5.9.2007,  17:47 Найти цитируемый пост)
 А если текст большой? Как работать с массивом символов и указателями?
Мой алгоритм совсем несложно преобразовать так, чтобы передавалась ссылка на строку, и в строке делать перестановки с помощью substr. Но я намеренно это не сделал, так как данную задачу оптимизировать нужно скорее по скорости, чем по памяти. А преобразовать один раз строку в массив и затем быстро переставлять элементы массива - это существенно быстрее, чем много-много раз делать substr.
Цитата(tishaishii @  5.9.2007,  18:09 Найти цитируемый пост)
Задача: алгоритм, который гарантировал бы перестановку =N% символов.
Так мой алгоритм как раз это и старается сделать, если $length($str) * $shuffle / 2 - целое число, то гарантированно, при невыполнении этого условия, но длинной строке - почти точно.

PM MAIL   Вверх
Ramirez
Дата 6.9.2007, 09:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 305
Регистрация: 18.1.2005
Где: Moscow, ExUSSR

Репутация: 4
Всего: 5



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

а из примеров tishaishii, как всегда узнаешь кучу необычных конструкций =)
PM ICQ   Вверх
amg
Дата 6.9.2007, 12:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50



Ramirez, если скорость работы действительно критична, то вот такое изменение кода приводит к ускорению в 20 раз:
Код

use List::Util qw(shuffle);
sub randomize {
  my @str = split '', $_[0];
  my $shuffle = int($_[1] * @str / 2);
  my @a = shuffle(0..$#str);
  while ($shuffle--) {
    my ($place1, $place2) = (shift @a, shift @a);
    # uc в следующей строке - для наглядности, из рабочего кода убрать
    ($str[$place1], $str[$place2]) = (uc $str[$place2], uc $str[$place1]);
  }
  return join '', @str;
}
Думаю, что по мелочам можно еще ускорить.

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

Это сообщение отредактировал(а) amg - 6.9.2007, 12:09
PM MAIL   Вверх
tishaishii
Дата 12.9.2007, 11:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8



и можно ещё железо докупить.
PM MAIL ICQ Skype   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Perl"
korob2001
sharq
  • В этом разделе обсуждаются общие вопросы по языку Perl
  • Если ваш вопрос относится к системному программированию, задавайте его здесь
  • Если ваш вопрос относится к CGI программированию, задавайте его здесь
  • Интерпретатор Perl можно скачать здесь ActiveState, O'REILLY, The source for Perl
  • Справочное руководство "Установка perl-модулей", можно скачать здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, korob2001, sharq.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Perl: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0852 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.