// codeart.ru / Вопрос/Ответ / Про скрытую сортировку и фильтрацию массивов Форум

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

Автор: Evgeniy 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) {
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 is($value) {
return create_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($data as $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 уже заложены и возможность сортировки, и возможность фильтрации, в результате в коде выполняется только обработка данных. Что, конечно же, способствует улучшению внешнего вида программы.

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

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


    // Эта функция пишется один раз и потом
    // может использоваться многократно
    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(); } }

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

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

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


  5. // Эта функция пишется один раз и потом
    // может использоваться многократно
    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’);

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

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

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

  9. Но в первом примере до рефакторинга был всего один проход по массиву, а после рефакторинга стало четыре. Если массивы маленькие, то может и ничего страшного, но ущерб производительности — налицо. К тому же можно поспорить о читабельности сочетания 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 приложений?

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

  11. Ромыч,

    К тому же можно поспорить о читабельности сочетания 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;

    }
    }

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

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

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

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

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

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

  16. Тормоз, ты прав, тут можно спорить. :-) Можно привести как примеры «за» так и «против». В каждом случае нужно думать отдельно как лучше организовать данные.

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

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

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

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

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

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

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

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

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

    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.

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

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

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

Leave a Reply

« »