Нужно проделать с массивом то, что обычно делают со строками:

Конечно, какой-то работающий код для массива у меня есть. Но, как обычно, интересует эффективность, в частности, можно ли обойтись без временного массива.

grep или map со splice

Не удастся с grep. grep возвращает массив.
Надо splice и for или while.


Это сообщение отредактировал(а) tishaishii - 22.3.2007, 13:31

my $a = 0; grep { defined ($_) ? $a++ : splice @a,$a,1 } @a

Можно вот так вот:

Отличие то что позволяет за один раз удалить несколько елементов... не вызывая splice каждому...

Писал прям в форум. но надеюсь понятно будет, возможно я не учел то что надо один оставлять пустой, но надеюсь сам сможешь исправить...

arto, твой код просто удаляет все пустые элементы, а это не совсем то, что нужно.

Проверил, работает:

"Нужно проделать с массивом то, что обычно делают со строками:
s/^\s+//; # Удаляем пустые элементы в начале" -- ?

arto, не придирайся,  то в начале, но не везде, да и мой код тогда неверен...
нужно тогда как для строк, три строки:

думаю так лучше всего будет

так что удалять-то надо?

Ну дык все просто, удаляем лидирующие пустые елементы и завершающие, внутри, если несколько подряд идущих, заменяем одним...

Что-то не видно оно.
Вот

Тут, думаю стоит уточнить, что имеется ввиду под "пустым" элементом. Пробельные символы, определенность елемента, или еще что, и уже подставлять необходимое сравнение в наши варианты...

Подойдет что угодно. Предлагаю для опреленности считать пустым элементом массива элемент, состоящий из символа "0" (ноль). Предлагаю также считать, что ведущих и ведомых нулей в массиве нет (их удалить несложно). Т.е., например, из 
('a', '0', 'b', '0', '0', 'c', '0', '0', '0', 'd')
должно получиться
('a', '0', 'b', '0', 'c', '0', 'd')

ЗЫ Господа! Примеры кода появляются быстрее, чем я успеваю в них разобраться, так что не обессудьте, сравнивать буду уже только завтра (а то у нас в Новосибирске дело к ночи).

Таак.
Что-то мне уже кажется, что надо удалять "пустые символы" не только по краям, но и везде, в середине удалять дубликаты?
Ну так задача гораздо упрощается.


Это сообщение отредактировал(а) tishaishii - 23.3.2007, 01:20

tishaishii, твой код работает не совсем так, как я имел в виду. Например,
a 0 b 0 0 0 0 0 0 0 0 0 c c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 d e
превращается в 
a 0 b 0 c c 0 0 0 0 0 0 0 d e
а я хочу получить
a 0 b 0 c c 0 d e

my ($a,$b) = (0,0); map { defined($_) ? ($a++,$b=0) : ($b++&&splice@a,$a++,1) } @a;
defined($a[0])||splice@a,0,1; defined($a[$#a])||splice@a,$#a,1;

Первые результаты тестирования.
Относительное время обработки массива:
Для меня оказалось совершенной неожиданностью, что (преобразование массива в строку)-(регулярное выражение)-(обратное преобразование строк в массив) работает быстро.

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

Это сообщение отредактировал(а) amg - 23.3.2007, 11:15

Попробовал на реальной задаче (когда элементы массива не одно-, а многосимвольные). Вариант с преобразованием массива в строку здесь здорово проигрывает остальным.

ну вот такой уплотненный код для уплотнения массива получился 



Как пустые элементы подразумевается или undef или 0 или строка нулевой длины

Это сообщение отредактировал(а) Nab - 23.3.2007, 12:20

да, ошибка была.

sub sq {
    my ($a,$b) = (0,0);
    map { defined($_) ? ($a++,$b=0) : ($b++?splice@_,$a,1:$a++); } @_;
    defined($_[0])||splice@_,0,1; defined($_[$#_])||splice@_,$#_,1;
    return @_;
}

(a,undef,undef,undef,undef,undef,undef,b) =>
 (a,undef,b)

(undef,undef,1,2,3,undef,undef,undef,4,undef,5,undef,undef,6,undef,undef) =>
 (1,2,3,undef,4,undef,5,undef,6)

(undef,undef,a,undef,undef,b,undef) =>
 (a,undef,b)

(undef,undef,a) =>
 (a)

(undef,a,undef) =>
 (a)

Ни какой map и grep по условиям задачи не годится.
Вот пробуй:

почему?

  DB<1> sub sq { my ($a,$b) = (0,0); map { $_ ? ($a++,$b=0) : ($b++?splice@_,$a,1:$a++); } @_; $_[0]||splice@_,0,1; $_[$#_]||splice@_,$#_,1; return @_; }

  DB<2> @arr=qw(0 0 a 0 b 0 0 0 0 0 0 0 c c 0 0 0 0 0 0 0 0 0 c c 0 0 0 0 0 0 c c 0 0 d e 0 0);

  DB<3> print '['.$_.']' foreach sq (@arr);
[a][0][b][0][c][c][0][c][c][0][c][c][0][d][e]
  DB<4>

Я вот тут подумал, что с grep еще красивее получиться может:

в данном случае создается второй массив.

http://forum.vingrad.ru/index.php?showtopi...t&p=1072959

my ($a,$b) = (0,0); map { $_ ? ($a++,$b=0) : ($b++?splice@a,$a,1:$a++); } @a; $_[0]||splice@a,0,1; $_[$#_]||splice@a,$#a,1;  -- где временный массив?

arto, это ты о чем говорил? об моем варианте или.... ?

А теперь по поводу временных массивов, не думаю что amg, имел ввиду буквально отсутствие временного массива, думаю он больше просил предложить вариант потребляющий меньше ресурсов, как памяти, так и времени....


этими словами он подозреваю имелл ввиду, что манипулирование элементами массива внутри map или grep плохая идея. Если обрабатывать значения массива можно, то изменять размер массива внутри цикла прохода по массиву не есть гуд.... Хорошо у нас тут удаление элементов, и подозреваю перл грамотно отрабатывает эту ситуацию, а если бы было добавление елементов, после текущей позиции или перед ней, что должен делать цикл? вернуться? или не учитывать добавление? а если вы изменяете елемент не текущий, то какой хотели бы обработать, со старым значением или с новым? Вообще это не корректный подход... Даже если он обрабатываеться сейчас по одному алгоритму, я не уверен что такое поведение присутствует во всех версиях перл, и останеться неизменным...

Единственно правильные варианты для splice считаю, while($i < @array) с самостоятельным контролем позиции в массиве. Я это реализовал у себя в первом варианте.

map и grep по большому счету фильтры, которые при этом позволяют обработать по очереди массив имитируя по сути внешний foreach или другой способ организации цикла. Но в большей степени, они могут отфильтровать и вернуть обработанный массив, что очень удобно, я почемуто взялся сразу за map, хотя по идее лучше подходил grep который избавил меня от одного внутреннего условия... Он возвращает елемент в результирующий список только при условии истинности своего выражения, тогда как для map мне пришлось имитировать возврат пустого списка, чтобы елементы не были включены в результирующий набор.

Возможно что и создается второй массив, но он создаеться внутри perl, и думаю вполне оптимально перераспределяется, тогда как использование splice внутри циклов заставляет перл делать еще один внутренний массив, и возможно не один :(... 

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

Это python более ли менее грамотно работает с оптимизацией памяти, т.к. везде, где можно неявно использует ссылки, а в Perl - проще, там онного нету.

map сейчас оптимизирован, и он не создает массива, если его не просят.
splice тем более.

Возможно, а при вызове slice из map? я к примеру не уверен, скорее даже наоборот....

splice манипулитует оригинальным массивом.
грубо говоря проверяем элемент массива по указателю.

Это вы про какую версию говорите?

Ну вот, потестировал. Тестируемый код приводить не буду, чтобы не занимать места. (arto-ref - это код arto с передачей массива по ссылке и модификацией его "по месту"). В колонке "Память" со знаком минус - это кол-во памяти, потребляеемой скриптом на создание массива. 

Nab-grep - это перл (в обоих смыслах). В коде tishaishii придется хорошо поразбираться, есть ради чего - дополнительная память почти не используется. Код arto удивительно быстро работает на "плотных" массивах - тоже надо поразбираться.

Господа! Всем большое спасибо.

Ой, действительно интересные результаты 
А почему мой первый вариант не включили, по моему он также будет наименее прожорлив, да и не вызывает slice для каждого елемента, то есть может дать выиграш на разреженном массиве...

Я его немного переделал, вполне удовлетворяет условиям задачи...

Добавлено через 13 минут и 48 секунд
А вот все мои варианты с передачей по ссылке, надеюсь будут менее прожорливы :(


Это сообщение отредактировал(а) Nab - 26.3.2007, 12:30

Кстати amg, свой вариант опубликуй...

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

Добавлено через 5 минут и 35 секунд
Да что-то он у меня сразу не пошел, а думать, в чем дело, было, как всегда, лень. Nab, завтра обязательно проверю твои новые варианты.


Это сообщение отредактировал(а) amg - 26.3.2007, 16:10

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


Добавлено через 2 минуты и 43 секунды
Ну большие массивы много и памяти будут кушать.
Значит, надо этот массив хранить на диске и обрабатывать поэлементно.


Добавлено через 2 минуты и 54 секунды
Ну большие массивы много и памяти будут кушать.
Значит, надо этот массив хранить на диске и обрабатывать поэлементно.

Nab, потестировал твой новый код. По потреблению памяти все осталось по-прежнему, зато заметно увеличилась скорость. Теперь compress_array_grep - абсолютный чемпион  . compress_array не использует дополнительную память, но у него есть такая неприятная особенность - с увеличением размера массива (каждый следующий набор данных в таблице соответствуют удвоенному массиву) резко растет время (кстати, ровно такая же ситуация с кодом tishaishii)

 

Прошу прощения, проблемы со связью.

Ну если ты не будешь хранить весь массив в оперативке, как у меня в примере для лучшего понимания, а когда-то запишешь однажды в файл с  разделителями, то память меняться почти не должна. Смысл-то цикл делать для записи в файл, в котором нет проверки на пустоту, а потом открывать этот файл, разбирать и заново его фильтровать. Вобщем, если будешь только читать из файла с разделителями, то будешь без напрягов работать с большими массивами, независимо от оперативки и подкачки.  Откуда ей рости во время чтения.

Это сообщение отредактировал(а) tishaishii - 27.3.2007, 10:42

Просто красивый код )))


Взято тут

Это сообщение отредактировал(а) G0rinich - 4.4.2007, 15:55