Про скрытую сортировку и фильтрацию массивов

Автор: Evgeny Sergeev

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

Что значит скрытая

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

Эти же рассуждения можно применить и к сортировке. Т.е. скрытая сортировка - это кода для нас важен порядок следования обрабатываемых элементов, но мы не осознаем это в явном виде. В результате рождается код, который можно упростить выполнив предварительную сортировку массива.

Скрытая фильтрация

Очень часто алгоритм решения той или иной задачи сводится к тому, что есть массив данных и для разных частей этого набора необходимо выполнить разные действия. Как правило решение подобной задачи выполняется с помощью следующего шаблона:

foreach($data as $val) {

  if ($val == "some value"){

         do_something($val);

  }

  if ($val == "another value"){

         do_something_else($val);

  }

}

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

$part = array_filter($data, create_function(‘$o’, ‘return $o == "some value";’));
array_walk($part, ‘do_something’);
$part = array_filter($data, create_function(‘$o’, ‘return $o == "another value";’));

array_walk($part, ‘do_something_else’);

В предложенном варианте код выглядит ~~значительно лучше~~ не на много лучше. В нем присутствует явное дублирование. Да и использование create_function не добавляет смысла. Поэтому применяем очередной рефакторинг и получаем вот такой код:

// Эта функция пишется один раз и потом
// может использоваться многократно
function is($value){
returncreate_function(‘$o’, ‘return$o == ‘.$value.’;’);
}
$part = array_filter($data, is(’some value’));

array_walk($part, ‘do_something’);
$part = array_filter($data, is("another value";’));

array_walk($part, ‘do_something_else’);

Вроде уже получше, но дублирование все так же мозолит глаза, поэтому делаем очередные изменения:

// Эта функция пишется один раз и потом
// может использоваться многократно
function is($value){
returncreate_function(‘$o’, ‘return$o == ‘.$value.’;’);
}
function run($numbers, $condition, $callback) {

$part = array_filter($numbers, $condition);

array_walk($part, $callback);

}
run($data, is(’some value’), ‘do_somthing’);

run($data, is(‘another value’), ‘do_something_else’);

Нужно отметить, что функции is и run - это функции которые мы задаем только один раз, а используем многократно. Фактически, в любом месте программы где есть foreach и if мы можно использовать функцию “run”. Т.е. в итоге мы получили довольно универсальный вариант обработки массивов. Для наглядности еще раз повторю код “до” и “после” рефакторинга. Разница, как говорится, на лицо:

foreach($dataas$val){
if($val == "some value"){

         do_something($val);
}
if($val == "another value"){

         do_something_else($val);
}
}
// VS
run($data, is(’some value’), ‘do_somthing’);

run($data, is(‘another value’), ‘do_something_else’);

Скрытая сортировка

Обычно скрытая сортировка проявляется задачах где нужно выполнить какие-то действия для максимального или минимального элемента из набора (критерии выбора могут быть другими). Шаблон кода выглядит следующим образом:

$max = $data[0];

foreach($data as $key => $val) {

  if ($val > $max) {

      $max = $val;

  }

}

do_somthing($max);

Вариант не очень красивый, все по тем же причинам - лишний цикл и ненужное условие. Мое решение такое:

rsort($data);

do_somthing($data[0]);

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

О базах данных и скрытых сортировках

Я уверен, что многие веб-программисты, читающие эту заметку, судорожно вспоминают случаи когда в их практике встречалась описанные выше конструкции. На самом деле, если разработка проекта ведется с использованием какой-либо СУБД вопрос о скрытой сортировке и фильтрации отпадает сам собой. Это связано с тем, что в SQL уже заложены и возможность сортировки, и возможность фильтрации, в результате в коде выполняется только обработка данных. Что, конечно же, способствует улучшению внешнего вида программы.

подписаться на блог

Тормоз

Гость

27 октября, 2010

Что-то на первый пример совсем плох, совсем вкусовщина. Ничего красивого не вижу, вариант с foreach гораздо лучше читается и быстрее понятен.
Evgeny Sergeev

Гость

27 октября, 2010

Тормоз, слишком прямолинейно судишь. Отрефактори предложенный мной вариант и совсем другая выразительность, вот например:

// Эта функция пишется один раз и потом
// может использоваться многократно
function is($value) {
return create_function(‘$o’, ‘return $o == ‘.$value.’;’);
}

$part = array_filter($data, is(’some value’));
array_walk($part, ‘do_something’);

$part = array_filter($data, is("another value";’));
array_walk($part, ‘do_something_else’);

Или вот пример:

// Эта функция пишется один раз и потом
// может использоваться многократно
function between($a, $b) {
return create_function(‘$o’, ‘return $o > ‘.$a.’ and $o <‘.$b.’;’);
}

$part = array_filter($numbers, between(10, 20));
array_walk($part, ‘do_something’);

$part = array_filter($numbers, between(20, 30));
array_walk($part, ‘do_something’);

$part = array_filter($numbers, between(30, 40));
array_walk($part, ‘do_something’);

Сравни вот с таким:

foreach($numbers as $val) {
if ($val >10 and $val < 20) {
do_somthing();
}
if ( $val > 20 and $val < 30){
do_somthing();
}
if ($val > 30 and $val < 40) {
do_somthing();
}
}

Тоже никакой разницы?
Evgeny Sergeev

Гость

27 октября, 2010

Блин, комментарий некорректно отобразился, щас поправлю!
Evgeny Sergeev

Гость

27 октября, 2010

Так же не стоит забывать, что использование if располагает к том,чтобы писать весь код непосредственно в if-е, а не выносить его в отдельную функцию. А это приводит к значительному распуханию.
Evgeny Sergeev

Гость

27 октября, 2010

// Эта функция пишется один раз и потом
// может использоваться многократно
function between($a, $b) {
return create_function(‘$o’, ‘return $o > ‘.$a.’ and $o <‘.$b.’;’);
}

$part = array_filter($numbers, between(10, 20));
array_walk($part, ‘do_something’);

$part = array_filter($numbers, between(20, 30));
array_walk($part, ‘do_something’);

$part = array_filter($numbers, between(30, 40));
array_walk($part, ‘do_something’);

Еще лучше будет так:

// Эта функция пишется один раз и потом
// может использоваться многократно
function between($a, $b) {
return create_function(‘$o’, ‘return $o > ‘.$a.’ and $o <‘.$b.’;’);
}

function run($numbers, $condition, $callback) {
$part = array_filter($numbers, $condition);
array_walk($part, $callback);
}

run($numbers, between(10, 20), ‘do_something’);
run($numbers, between(20, 30), ‘do_something’);
run($numbers, between(30, 40), ‘do_something’);
Тормоз

Гость

27 октября, 2010

Убедил, вообще-то очень интересное решение, я так сразу с плеча рубанул, наверно, просто потому что непривычный подход. Но плохие привычки надо истреблять.
Evgeny Sergeev

Гость

27 октября, 2010

Тормоз, на самом деле, мне не нравится использовать create_function, вместо нее гораздо лучше использовать лямбда функции + замыкания. Но это только с PHP 5.3., а так как многие еще сидят на более ранних версиях PHP, привел пример с create_function.
Ну и имена функций + переменных нужно другими делать… Наверное, еще один пост надо писать
Тормоз

Гость

27 октября, 2010

Пиши, конечно! Обсудим. В том числе и отдельно про примеры с лямбда-функциями и замыканиями. У тебя очень полезные заметки.
Ромыч

Гость

27 октября, 2010

Но в первом примере до рефакторинга был всего один проход по массиву, а после рефакторинга стало четыре. Если массивы маленькие, то может и ничего страшного, но ущерб производительности - налицо. К тому же можно поспорить о читабельности сочетания array_filter/array_walk, но это субъективно. В данный момент мне интересен вопрос производительности. Кстати, поиск максимального элемента с помощью сортировки тоже выглядит сомнительно в этом свете.

Почему бы не отрефакторить с одним проходом? Например, как-нибудь так:

function process_item($val, $key)
{
if ($val == “some value”){
do_something($val);
}
else if ($val == “another value”){
do_something_else($val);
}
}
…
array_walk($arr, ‘process_item’);

Функцию process_item тоже можно отрефакторить при желании, но в любом случае все приведенные здесь примеры решаются в один проход по массиву, что положительно сказывается на производительности. Или производительность не важна для php приложений?
Тормоз

Гость

27 октября, 2010

Ромыч, производительность важна в контексте применения, а не для PHP-приложений вообще.
Evgeny Sergeev

Веб-разработчик, автор блога codeart.ru

27 октября, 2010

Ромыч,

К тому же можно поспорить о читабельности сочетания array_filter/array_walk, но это субъективно.

Спорить нужно не о array_filter/array_walk, а вот о таких вариантах:

run($numbers, between(10, 20), ‘do_something’);
run($numbers, between(20, 30), ‘do_something’);
run($numbers, between(30, 40), ‘do_something’);

и

foreach($numbers as $val) {
if ($val > 10 and $val < 20){
do_somthing();
}
if ($val > 20 and $val < 30) {
do_somthing();
}
if ($val > 30 and $val > 40) {
do_somthing();
}
}

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

Интересно увидеть Ваш вариант, скажем вот такой функции:

function consent($qid)
{
global $write, $set, $queue, $stat;
if (isset($queue[‘items’][$qid]))
{
$stat[‘mode’] = $set[‘mode’];
$stat[‘limit’] = $set[‘limit’];
$stat[‘items’][$qid] = $queue[‘items’][$qid];
$stat[‘items’][$qid][‘time’] = time();
$stat[‘items’][$qid][‘views’] = $stat[‘items’][$qid][‘clicks’] = ‘0′;

if ($set[‘mode’] == ‘daos’)
{
foreach ($stat[‘items’] as $key => $val)
{
if (!isset($val[‘viewsNeed’]))
$linesDaosMode[] = $key;
}
$linesOut = array_slice($linesDaosMode, 0, -$set[‘limit’]);
}

$queue[‘items’][$qid][‘time’] = 0;
foreach ($queue[‘items’] as $key => $val)
{
if ($val[‘time’] + 3600 > time())
{
$clean[$key] = $val;
}
else
{
$num = $val[‘SMS’];
$queue[‘SMS’][$num] = ”;
}
}
unset($queue[‘items’]);
$queue[‘items’] = $clean;

if (!empty($linesOut))
foreach ($linesOut as $key => $id)
{
lineOut($id);
}

if (isset($stat[‘items’][‘заглушка’]))
unset($stat[‘items’][‘заглушка’]);

$write[’stat’] = $write[‘queue’] = 1; static $write;

}
}
Тормоз

Гость

27 октября, 2010

Ой, узнаю функцию. Страшна как смерть
В ней изначально ещё и отправка мыла была, lineOut появилась уже после недавней декомпозиции (но всё равно ужасно осталось, просто чуть лучше).
Тормоз

Гость

27 октября, 2010

Парсер у тебя балда.
Evgeny Sergeev

Веб-разработчик, автор блога codeart.ru

27 октября, 2010

Тормоз, парсер - балда. Факт!

Еще одна мысль, которая не высказана выше, но очень важна. Вот Романыч обратил внимание на то, что мой вариант избыточен в плане производительности. И это так. Но! На самом деле избыточность возникает не из пустого места. Корень зла в том, что структура данных спроектирована неудачно. Фактически, если данные требуют разной обработки, то скорее всего их НЕ нужно группировать вместе.

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

Гость

27 октября, 2010

Ну это спорно насчёт группировки, хотя вот именно в моём случае можно было бы попробовать другие варианты. Всё же данные групируются прежде всего по принадлежности к объекту, а не для удобства различной обработки, IMHO.
Evgeny Sergeev

Веб-разработчик, автор блога codeart.ru

27 октября, 2010

Тормоз, ты прав, тут можно спорить. Можно привести как примеры “за” так и “против”. В каждом случае нужно думать отдельно как лучше организовать данные.
nekufa

Гость

27 октября, 2010

Очень аппетитно выглядит
Я думаю, это хороший подход для сокращения рутины!
Тормоз

Гость

28 октября, 2010

И всё же как-то не по душе мне такой способ.

Сейчас поэкспериментировал с твоими вариантами, набросал собственную лямбда-функцию, прикольно, да… но на мой взгляд, читаемость всё же на порядок хуже. Скорей всего это сильно субъективно, конечно, но я foreach с условиями понимаю отлично, а вот твои штуки с run как-то напрягать мозг приходится.

Сейчас продолжаю мучать свой первый класс, и всё же, пожалуй, оставлю там foreach в подобных местах.
Тормоз

Гость

28 октября, 2010

Хм. И всё же не удержался, применил лямбда-функцию. На самом деле вроде попроще получается, чем обход массива. Хотя запись мне не нравится. Покажу потом.
Evgeny Sergeev

Веб-разработчик, автор блога codeart.ru

28 октября, 2010

Тормоз, ну значит используй свой вариант. В любом случае у тебя есть место для маневра.
Ромыч

Гость

28 октября, 2010

Спасибо, я в общем-то понял общий принцип - здесь не настолько заметно падение производительности, насколько заметно падение эффективности поддержки такого кода. Тут я не могу не согласиться

Однако, не могу и воздержаться от комментариев Имхо, конечно.

Вот в этом конкретном примере:

run($numbers, between(10, 20), ‘do_something’);
run($numbers, between(20, 30), ‘do_something’);
run($numbers, between(30, 40), ‘do_something’);

Согласен, что такой подход обоснован, если для разных интервалов должны вызываться разные функции. А если функция одна и та же, то элегантнее это сделать за одну операцию.

Что же касается функции consent - страшненькая, конечно. Не возмусь рефакторить функцию, вырванную из контекста, но для начала вижу несколько мест. Могу и ошибаться, потому что проверить работоспособность не представляется никакой возможности. Так что ногами меня сильно не бейте

1) foreach($linesOut) в конце функции можно втащить под условие if ($set['mode'] == ‘daos’). А далее можно всё, что находится в этом if’е выделить в отдельную функцию, например lineOutItemsForDaosMode($stat['items']). Сам цикл for_each($linesOut) можно заменить на array_walk.

2) foreach($queue['items']) тоже можно вынести в отдельную функцию. Тогда по идее можно быдет это место заменить вызовом, подобным этому:
$queue[‘items’] = createArrayAndResetSms($queue['items'], $queue['SMS']);
(Вообще, этот цикл мне не очень нравится, потому что в в нем выполняются разные по смыслу действия - создается массив и обнуляются значения в другом массиве. Тут надо бы по-другому данные формировать…)

3) Ну и если не ошибаюсь можно unset вызывать без проверки на isset.

В общем, как-то так. А дальше по обстоятельствам
Тормоз

Гость

28 октября, 2010

Ромыч, работоспособность функции можно проверить, если скачать версию AvisoDaos (можно просто 0 поставить в цене) - http://brokenbrake.biz/AvisoDaos/

Про unset не знал, проверил - действительно, даже варнингов никаких, хотя удалялась несуществующая переменная. Интересно.