Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Системное программирование > Перемешать данные

Автор: wkd 17.8.2009, 15:54

Возникла проблемма, прошу помочь с решением.
На входе имеется строка, вида: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccddddddddddeeeee"
Необходимо перемешать все данные случайным образом, чтоб на выходе получить что-то похожее на: "...dacbbcdaaabceda...". Как это сделать, по возможности качественно перемешать все и быстро? Голову сломал, нашел лишь похожую проблемму http://forum.vingrad.ru/topic-170846.html, но так и не разобрался, уровень знание пока не тот, а сделать надо. Помогите пожалуйста!
PS: даже при одинаковой вводной, конечный результат должен быть случайным.

Автор: ginnie 17.8.2009, 16:07

wkd, предлагаю "нетрадиционный" вариант

Код


my $in="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccddddddddddeeeee";
print join("", sort {int(rand(3))-1} split(//, $in));

Автор: wkd 17.8.2009, 16:15

Огромное спасибо, работает быстро даже при большом вводном массиве! Мои изыски подвешивали машинку=((( Есть куда стремиться! Но есть ли возможность перемешать данные более качественно? Пример, вводные:
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccddddddddddddddddddddeeeeeeeeeeeeeeeeeeee
Вывод следующий:
eseloesbeeosssbbossbssssbsblslsssssslsebelleelbeeebbeeeeoleeeboeblblbobblbblbbllllloololoooloooooooo
Под час повторение значений еще более жесткое! Можно ли перемешать качественнее? Пропускать строку так несколько раз, заметно замедляет работу=(

Автор: ginnie 17.8.2009, 16:25

Да не за что, этого добра у нас полно (традиционный вариант):

Код


my $in="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccddddddddddeeeee";
my @out;
my $dimension = length $in;
for my $symbol (split //, $in) {
    my $index = int rand($dimension);
    while(defined $out[$index++]) {
        $index %= $dimension;
    }
    $out[--$index] = $symbol;
}
print join "", @out;

Автор: wkd 17.8.2009, 16:33

Спасибо, второй вариант лучше=)

Автор: KSURi 17.8.2009, 21:48

Тоже, вроде, традиционный:

Код


use List::MoreUtils qw(uniq);

my $str = 'aaaaabbbbbbbbbccccccccddddddddeeeeeeee';
my @chars = uniq split //, $str;
my $random = join '', map($chars[int rand scalar @chars], 1 .. length $str)

Автор: ginnie 17.8.2009, 21:52

KSURi, а ты уверен в корректности своего кода? Для "ab" он случайно "aa" не может выдать?

Автор: KSURi 17.8.2009, 22:56

Может, не подумал об этом. Но судя по входным данным такого не будет.

Автор: amg 18.8.2009, 07:48

Можно так:

Код

use List::Util qw(shuffle);
my $in="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccddddddddddeeeee";
print (join '', shuffle(split //, $in));

Функция shuffle из стандартного модуля List::Util работает быстро, в несколько раз быстрее, чем последний код ginnie. Но, впрочем, когда я вставил код функции из модуля в основную программу, ускорение практически исчезло. smile

Автор: ginnie 18.8.2009, 10:07

Цитата(amg @ 18.8.2009, 07:48

)

Но, впрочем, когда я вставил код функции из модуля в основную программу, ускорение практически исчезло.

amg, ты говоришь про код функции shuffle()? Там же XS. Или ты взял код из List::Util::PP?

Автор: amg 18.8.2009, 10:46

Цитата(ginnie @ 18.8.2009, 10:07

)

amg, ты говоришь про код функции shuffle()? Там же XS. Или ты взял код из List::Util::PP?

Да, а я и не заметил, действительно XS. За счет этого основное ускорение. Но в List::Util есть и "обыкновенный" код, весьма быстрый и хитрый (для меня), его можно вставить в свой код:

Код

sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;
}

Автор: KSURi 18.8.2009, 13:02

Практически мой любимый модуль, а про shuffle() забыл...