@jinxonik / UniLecs #148

zerotoend.cpp

// Наиболее полная коллекция методов :))

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using std::cout;
using std::vector;
using std::list;

//#define OPTIMIZED_METHOD1  // оптимизировать метод №1

// МЕТОД №1: удаление элементов массива (вектора) с добавлением нулей в конец.
// Перебираем все элементы массива от конца (кроме последнего) к началу и удаляем все нули.
// В конце восстанавливаем первоначальный размер массива путём добавления нулей в конец.
void zero_to_end1(vector<int> &array)
{
  size_t size = array.size();
#if !defined(OPTIMIZED_METHOD1)
  // Поэлементный вариант удаления (наиболее неоптимизированный)
  if (size < 2) { return; }
  for (auto n = array.end()-2; n >= array.begin(); --n) {
    if (*n == 0) { array.erase(n); }
  }
#else
  // Использование оптимизированного варианта (с комбинацией методов erase() и std::remove())
  // вместо цикла уменьшает сложность, т.к. в этом случае копирования каждого из последующих
  // элементов на одну позицию влево не происходит, и работа будет похожа на метод №2. Однако
  // отладка показывает, что метод №2 (см. ниже) даже в этом случае работает более оптимально
  // (по крайней мере, в G++).
  array.erase(std::remove(array.begin(), array.end(), 0), array.end());
#endif
  array.resize(size, 0);
}

// МЕТОД №1A: удаление элементов двусвязного списка с добавлением нулей в конец.
// Удаляем все нули и восстанавливаем первоначальный размер путём добавления нулей в конец.
// Этот метод должен быть более быстрым, чем метод №1, т.к. удаление элементов из двусвязного
// списка происходит без копирования каждого из последующих элементов на одну позицию влево.
void zero_to_end1a(list<int> &array)
{
  size_t size = array.size();
  array.remove(0);
  array.resize(size, 0);
}

// МЕТОД №2: копирование ненулевых элементов массива (вектора) с добавлением нулей в конец.
// Чтобы исключить при каждом удалении копирование каждого из последующих элементов на одну позицию
// влево, будем копировать ненулевые значения в тот же вектор, а остаток вектора заполнять нулями.
// Самый нормальный метод (вместе с 2А).
void zero_to_end2(vector<int> &array)
{
  auto next = std::remove_copy(array.begin(), array.end(), array.begin(), 0);
  std::fill(next, array.end(), 0);
}

// МЕТОД №2А: небольшая оптимизация копирования ненулевых элементов массива (вектора).
// Зачем копировать первые элементы, когда можно найти первый ноль и начать копирование со
// следующего элемента? Это не всегда может дать ускорение (оно будет не столь значительным и
// вероятнее всего для массивов, в начале которых много ненулевых элементов, либо все ненулевые).
void zero_to_end2a(vector<int> &array)
{
  auto el = std::find(array.begin(), array.end(), 0);
  if (el != array.end()) {
    el = std::remove_copy(el + 1, array.end(), el, 0);
    std::fill(el, array.end(), 0);
  }
}

// МЕТОД №3: использование функции сортировки в двусвязном списке.
// Значения при сортировке меняются местами, только если второй аргумент равен нулю.
// Почему работает именно такое условие, а не "если первый аргумент не равен нулю" ?
// Дело в том, что в методе sort используется устойчивая сортировка (порядок равных элементов
// сохраняется), а функция сравнения возвращает true, если a < b. Следовательно перемещение
// элементов производится только при возвращении значения true (иначе нельзя было бы понять,
// больше ли первый элемент второго [и его нужно переместить вниз] или равен ему [не трогать]).
// Не самый оптимальный вариант, но самый короткий в записи (гольф) :)
void zero_to_end3(list<int> &array)
{
  array.sort([](int a, int b) { return b == 0; });
}

// МЕТОД №3А: аналог метода №3, но для вектора.
void zero_to_end3a(vector<int> &array)
{
  std::stable_sort(array.begin(), array.end(), [](int a, int b) { return b == 0; });
}

// МЕТОД №4: разворачивание подмассивов.
// Примем за begin начало массива, а за end его конец. Пока эти два указателя не встретятся
// (в т.ч. при поиске), повторяем следующие действия. Найдём первый нулевой элемент, начиная с
// begin (результат запишем в begin) и последний ненулевой, начиная с end (в обратном порядке;
// результат запишем в end). Развернём элементы массива (переставим в обратном порядке) от begin
// до end. Снова найдём последний ненулевой элемент (end) и снова развернём элементы от begin до
// нового end. Увеличим begin на 1 (поскольку он точно не будет указывать на 0). Повторим.
// Использовать этот метод в реальной задаче не стоит, он сделан чисто для прикола :)
// p.s. Если вам не нравится "не очень хорошая читаемость кода" (присваивание в while,
//      декремент (--) в if), см. комменты и всё поймёте! :)
void zero_to_end4(vector<int> &array)
{
  auto begin = array.begin(), end = array.end();
  while ((begin = std::find(begin, end, 0)) != end) {  // пока есть нули
    for (int i = 2; i > 0; --i) {  // два прохода
      do {
        if (--end == begin) return;  // выходим, если дошли до начала
      } while(*end == 0);  // ищем последний не ноль
      std::reverse(begin, end + 1);  // второй параметр должен указывать на элемент ЗА последним
    }
    ++begin; ++end;  // end должен указывать на элемент ЗА последним
  }
}

// МЕТОД №5: использование функции stable_partition.
// В C++ есть функция std::stable_partition, которая упорядочивает элементы таким образом, чтобы
// все элементы, удовлетворяющие определённому условию шли в начале, а остальные - в конце,
// сохраняя при этом относительный порядок элементов.
// Несмотря на кажущуюся оптимальность, это не очень хороший вариант, т.к. использует для работы
// дополнительную память :(
void zero_to_end5(vector<int> &array)
{
  std::stable_partition(array.begin(), array.end(), [](int n) { return n != 0; });
}

////////////////////////////////////////////////////////////////////////////////////////////////////

template < typename T >
void show_array(const char *text, T &array)
{
  cout << text << ": [";
  bool comma = false;
  for (int n : array) {
    if (comma) { cout << ","; }
    cout << " " << n;
    comma = true;
  }
  cout << " ]\n";
}

void task148(vector<int> &array)
{
  show_array<vector<int>>("  Source ", array);

  vector<int> vec;
  vec = array;
  zero_to_end1(vec);
  show_array<vector<int>>("Method 1 ", vec);

  list<int> lst;
  for (int n : array) { lst.push_back(n); }
  zero_to_end1a(lst);
  show_array<list<int>>("Method 1A", lst);

  vec = array;
  zero_to_end2(vec);
  show_array<vector<int>>("Method 2 ", vec);

  vec = array;
  zero_to_end2a(vec);
  show_array<vector<int>>("Method 2A", vec);

  lst.clear();
  for (int n : array) { lst.push_back(n); }
  zero_to_end3(lst);
  show_array<list<int>>("Method 3 ", lst);

  vec = array;
  zero_to_end3a(vec);
  show_array<vector<int>>("Method 3A", vec);

  vec = array;
  zero_to_end4(vec);
  show_array<vector<int>>("Method 4 ", vec);

  vec = array;
  zero_to_end5(vec);
  show_array<vector<int>>("Method 5 ", vec);

  cout << "\n";
}

int main()
{
  vector<int> array;

  array = { 0, 0, -5, 4, 0, 2, 0 };
  task148(array);

  array = { 4, 0, 6, 0, 0, -5 };
  task148(array);

  array = { 1, 2, 3, 4, 5, 6 };
  task148(array);

  cout << "Press Enter to exit...";
  std::cin.get();
  return 0;
}

zerotoend.dpr

// Delphi XE2+

{$APPTYPE CONSOLE}
uses System.Types;

// Копирование ненулевых элементов массива в себя с добавлением нулей в конец.
procedure ZeroToEnd(var Arr: TIntegerDynArray);
var Idx, N: Integer;
begin
  Idx := 0;  // индекс для записи значений
  for N in Arr do
    if N <> 0 then
    begin
      Arr[Idx] := N;
      Inc(Idx);
    end;
  for Idx := Idx to High(Arr) do
    Arr[Idx] := 0;
end;

procedure Task148(const Arr: TIntegerDynArray);

  procedure ShowArr(const Txt: String; const Arr: TIntegerDynArray);
  var i: Integer;
  begin
    Write(Txt, ': [');
    for i := 0 to High(Arr) do
    begin
      if i > 0 then Write(',');
      Write(' ', Arr[i]);
    end;
    WriteLn(' ]');
  end;

var Temp: TIntegerDynArray;
begin
  Temp := Arr;
  ShowArr('Source', Temp);
  ZeroToEnd(Temp);
  ShowArr('Result', Temp);
  WriteLn;
end;

begin
  Task148(TIntegerDynArray.Create(0, 0, -5, 4, 0, 2, 0));
  Task148(TIntegerDynArray.Create(4, 0, 6, 0, 0, -5));
  Task148(TIntegerDynArray.Create(1, 2, 3, 4, 5, 6));
end.

zerotoend.fasm

; fasm 1

format	PE Console 4.0
entry	start

include	'win32axp.inc'

;-- CODE SECTION -------------------------------------------------------------------------------------------------------

.code

start:

		cld
		stdcall	ShowArray, 'Source'

		mov	edx,Count		; number count (> 0)
		mov	ecx,edx			; zero count
		mov	esi,Numbers		; pointer for loading
		mov	edi,esi			; pointer for storage
	.next:
		lodsd				; load
		test	eax,eax
		jz	@F			; skip if zero
		stosd				; else store
		dec	ecx			; and decrase zero count
	@@:
		dec	edx
		jnz	.next			; loop

		xor	eax,eax
		rep stosd			; store ecx zeros

		stdcall	ShowArray, 'Result'

		invoke	getch, 0
		invoke	ExitProcess, 0

; Output array
proc		ShowArray Message
		cinvoke	printf, '%s: [', [Message]
		mov	esi,Numbers
		mov	ebx,Count
		jmp	@F
	.next:	cinvoke	printf, ','
	@@:	lodsd
		cinvoke	printf, ' %i', eax
		dec	ebx
		jnz	.next
		cinvoke	printf, <' ]',10>
		ret
endp

;-- DATA SECTION -------------------------------------------------------------------------------------------------------

.data

Numbers		dd	0, 0, -5, 4, 0, 2, 0
Count		=	($-Numbers)/4

;-- IMPORT SECTION -----------------------------------------------------------------------------------------------------

section	'.idata' import data readable

library	kernel32, 'kernel32.dll',\
	msvcrt, 'msvcrt.dll'

	import_kernel32
	all_api

import	msvcrt,\
	printf, 'printf',\
	getch, '_getch'

zerotoend.gs

# GolfScript: http://golfscript.apphb.com/?c=WzAgMCAtNSA0IDAgMiAwXQouMC0uLEAsXC1bMF1cKisnLCcq
;[0 0 -5 4 0 2 0]
.0-.,@,\-[0]\*+','*

zerotoend.py

# Формируем новый массив из ненулевых элементов, добавляя нули в конец
def zero_to_end(arr):
  idx = 0  # индекс для записи
  for n in arr:
    if n != 0:
      arr[idx] = n
      idx += 1
  for i in range(idx, len(arr)):
    arr[i] = 0

def task148(arr):
  print("Source:", arr)
  zero_to_end(arr)
  print("Result:", arr)
  print()

task148([0, 0, -5, 4, 0, 2, 0])
task148([4, 0, 6, 0, 0, -5])
task148([1, 2, 3, 4, 5, 6])

zerotoend.rb

# МЕТОД №1: удаление элементов массива с добавлением нулей в конец.
# Перебираем все элементы массива от конца (кроме последнего) к началу и удаляем все нули.
# В конце восстанавливаем первоначальный размер массива путём добавления нулей в конец.
def zero_to_end1(arr)
  len = arr.length
  if len < 2; return; end
  arr.delete(0)
  (len-arr.length).times { arr << 0 }
end

# МЕТОД №1A: удаление элементов хэша с добавлением нулей в конец.
# Удаляем все нули и добавляем нули с новыми индексами, пока размер не станет прежним.
# Этот метод должен быть более быстрым, чем метод №1, т.к. удаление элементов из хэша
# происходит без копирования каждого из последующих элементов на одну позицию влево.
def zero_to_end1a(arr)
  len = arr.length
  if len < 2; return; end
  arr.delete_if { |i, n| n == 0 }
  (len-arr.length).times { |n| arr[len+n] = 0 }
end

# МЕТОД №2: копирование ненулевых элементов массива с добавлением нулей в конец.
# Чтобы исключить при каждом удалении копирование каждого из последующих элементов на одну позицию
# влево, будем копировать ненулевые значения в тот же массив, а остаток заполнять нулями.
# Самый нормальный метод.
def zero_to_end2(arr)
  idx = 0  # индекс для записи
  arr.each { |n|
    if n != 0
      arr[idx] = n
      idx += 1
    end
  }
  (idx...arr.length).each { |i|
    arr[i] = 0
  }
end

# МЕТОД №3: использование сортировки.
# Выполняем любую устойчивую сортировку (например, вставками), только вместо сравнения 2-х
# элементов проверяем - является ли предыдущий элемент нулевым
def zero_to_end3(arr)
  (1...arr.length).each { |i|
    key, j = arr[i], i
    while j > 0 && arr[j-1] == 0
      arr[j] = arr[j-1]
      j -= 1
    end
    arr[j] = key
  }
end

# МЕТОД №4: разворачивание подмассивов.
# Примем за first индекс начала массива, а за last - индекс конца. Пока они не встретятся
# (в т.ч. при поиске), повторяем следующие действия. Найдём первый нулевой элемент, начиная с
# first (результат запишем в first) и последний ненулевой, начиная с last (в обратном порядке;
# результат запишем в last). Развернём элементы массива (переставим в обратном порядке) от first
# до last. Снова найдём последний ненулевой элемент (last) и снова развернём элементы от first до
# нового last. Увеличим first на 1 (поскольку он точно не будет указывать на 0). Повторим.
# Использовать этот метод в реальной задаче не стоит, он сделан чисто для прикола :)
def zero_to_end4(arr)
  first, last = 0, arr.length-1
  loop do
    first = arr.index(0)
    if first == nil || first >= last; return; end
    2.times {
      last = arr.rindex { |n| n != 0 }
      if last == nil || last <= first; return; end
      arr[first..last] = arr[first..last].reverse
    }
    first += 1
  end
end

# МЕТОД №5: разделение массива с последующим объединением.
# Делим массив на 2 части по критерию с помощью partition, а затем объединяем их
# (partition - почти аналог std::stable_partition из C++)
def zero_to_end5(arr)
  arr[0...arr.length] = arr.partition { |n| n != 0 }.flatten
end

################################################################################

def task148(*arr)
  puts "  Source : #{arr}"

  temp = arr.clone
  zero_to_end1(temp)
  puts "Method 1 : #{temp}"

  temp = {}
  arr.each_with_index { |n, i| temp[i] = n }
  zero_to_end1a(temp)
  puts "Method 1A: #{temp.values}"

  temp = arr.clone
  zero_to_end2(temp)
  puts "Method 2 : #{temp}"

  temp = arr.clone
  zero_to_end3(temp)
  puts "Method 3 : #{temp}"

  temp = arr.clone
  zero_to_end4(temp)
  puts "Method 4 : #{temp}"

  temp = arr.clone
  zero_to_end5(temp)
  puts "Method 5 : #{temp}"
  puts
end

task148(0, 0, -5, 4, 0, 2, 0)
task148(4, 0, 6, 0, 0, -5)
task148(1, 2, 3, 4, 5, 6)