Форум PHP программистов > Задачка. Подскажите, бьюсь второй день

[ Поиск ] - [ Пользователи ] - [ Календарь ]

Полная Версия: Задачка. Подскажите, бьюсь второй день

Krevedko

6.08.2009 - 22:46

Не могу доделать код

PHP

<?php 
//Дан массив почтовых адресов
$massiv = array("......"
);
$quantity=count($massiv);
for ($i=0; $i<$quantity; $i++)
{
    $domain = strrchr ($massiv[$i] , "@"); 
    if  (isset($list[$domain]) && is_array($list[$domain]))
    {                                                                                     
       array_push($list[$domain],$massiv[$i]);                                             
       $list_cnt[$domain]++;
    } 
    else 
    {
        $list[$domain] = array($massiv[$i]);
        $list_cnt[$domain] = 1;
     }
}

Это мы раскидали все в массивы вида $list['one.net'][], $list['two.net'][] итд.
А также знаем, сколько элементов в каждом (массив $list_cnt[$domain]).

Теперь видимо надо определить, в каком массиве больше всего элементов.
Т.е. видимо надо сравнивать каждый последующий $list[$domain] с предыдущим.
Т.е. в цикл выше включить что-то вроде

PHP

if (count($list[$domain]) < count($list[strrchr ($massiv[$i] , "@")]))
{
    unset ($max[$domain])
    $max[strrchr ($massiv[$i] , "@")]=count($list[strrchr ($massiv[$i] , "@")]);
}

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

Спустя 47 минут, 24 секунды (6.08.2009 - 22:33) FatCat написал(а):

Цитата (Krevedko @ 6.08.2009 - 22:46)

были распределены равномерно

Нужно определиться со словом "равномерно".

Спустя 49 секунд (6.08.2009 - 22:34) kirik написал(а):

Вот честно, не много понял. Один пример лучше десятка объяснений, покажи "на кошках" что нужно получить из исходного массива адресов ($massiv)?

Спустя 13 часов, 25 минут, 4 секунды (7.08.2009 - 11:59) Alchemist написал(а):

тогда пока все делается правильно. я вижу алгоритм так:

1) группировка мыла по серверу - сделано
2) сортировка групп обратно кол-ву (опционально)
3) вытаскивается каждая группа по очереди и равномерно распределяется среди вытащеных прежде.

Если сортировку в пункте 2 не делать - распределение будет зависить от расположения групп, т.е. работать будет, но теоретически будет менее равномерным...

Спустя 1 час, 36 минут, 8 секунд (7.08.2009 - 13:35) sergeiss написал(а):

А почему бы просто не использовать уже готовые функции array_rand или shuffle?

Спустя 4 часа, 40 минут, 2 секунды (7.08.2009 - 18:15) Krevedko написал(а):

Потому что, читайте выше, мне не надо случайно разбросать элементы.

Цитата

1) группировка мыла по серверу - сделано
2) сортировка групп обратно кол-ву (опционально)
3) вытаскивается каждая группа по очереди и равномерно распределяется среди вытащеных прежде.

это я и так знал ))
По существу будут предложения решения ? ))

Спустя 41 минута, 24 секунды (7.08.2009 - 18:57) kirik написал(а):

Задачка интересная (вот только непонятно зачем такое нужно).

Вот что вышло

PHP

$mails = array(
    'john@one.net',
    'alex@one.net',
    'max@one.net',
    'peret@two.com',
    'mike@two.com',
    'jack@two.com',
    'mama@three.com',
    'papa@three.com',
    'sister@three.com',
    'brother@three.com',
    'unkle@three.com',
    'aunt@three.com',
);

function cmp($a, $b)
{
    $ca = count($a);
     $cb = count($b);
    if($ca == $cb)
        return 0;
    return ($ca > $cb) ? -1 : 1;
}

$array = array();
for($i = 0, $c = count($mails); $i < $c; $i++)
{
    $host = ltrim(strstr($mails[$i], '@'), '@');
    $array[$host][] = $mails[$i];
}
usort($array, 'cmp');

$new_array = array();

$last = count($array) - 1;
while(!empty($array[0]))
{
    for($i = 0, $c = count($array); $i < $c; $i++)
    {
        for($si = 0, $sc = $c; $si < $sc; $si++)
        {
            if(isset($array[$i][0]))
                $new_array[$si][] = array_shift($array[$i]);
            else
                continue;
        }
    }
}

$array = array();
for($i = 0, $c = count($new_array); $i < $c; $i++)
{
    $array = array_merge($array, $new_array[$i]);
}

print_r($array);
// Array
// (
//     [0] => mama@three.com
//     [1] => peret@two.com
//     [2] => john@one.net
//     [3] => brother@three.com
//     [4] => papa@three.com
//     [5] => mike@two.com
//     [6] => alex@one.net
//     [7] => unkle@three.com
//     [8] => sister@three.com
//     [9] => jack@two.com
//     [10] => max@one.net
//     [11] => aunt@three.com
// )

наверняка можно как-то упростить, щас спросони не варит голова

Спустя 30 минут, 20 секунд (7.08.2009 - 19:27) Krevedko написал(а):

То, что нужно..
О ! Новые функции....почитаю -ка я мануал.
Спасибо за код !!!

А можно теперь тему грохнуть ? )))

Спустя 9 минут, 21 секунда (7.08.2009 - 19:37) kirik написал(а):

Цитата (Krevedko @ 7.08.2009 - 11:27)

А можно теперь тему грохнуть

А с какой целью интересуетесь?

Спустя 51 секунда (7.08.2009 - 19:37) Krevedko написал(а):

Щас буду разбираться. Может улучшить получится

Спустя 8 минут, 59 секунд (7.08.2009 - 19:46) kirik написал(а):

Цитата (Krevedko @ 7.08.2009 - 11:37)

это задачка на собеседование

Как же ты работать будешь?

ЗЫ. Отредактируй свой пост просто..

Спустя 10 минут, 6 секунд (7.08.2009 - 19:56) Krevedko написал(а):

Ладно, проехали ))

Спустя 9 минут, 47 секунд (7.08.2009 - 20:06) glock18 написал(а):

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

Ну да спрашивайте, чего непонятно)) Объясню, пока здесь сижу.

Вот оно - мое детище...

PHP

function cmp($a, $b)
{
    $ca = count($a);
     $cb = count($b);
    if($ca == $cb)
        return 0;
    return ($ca > $cb) ? -1 : 1;
}

function needPush($iteration, $total, &$hostArray, &$currCount)
{
    if ($iteration == 0) return true;
    
    $hostIndex = key($hostArray);
    if ($hostIndex == 0) return true;
    
    if (empty($currCount))
        $currCount = sizeof($hostArray);
        
    $k = $hostIndex / $iteration;
    echo $k . ' - ' . ($currCount / $total) . '<br />';
    if ($k <= $currCount / $total)
        return true;
    
    return false;
}

$array = array();
for($i = 0, $c = count($mails); $i < $c; $i++)
{
    $host = ltrim(strstr($mails[$i], '@'), '@');
    $array[$host][] = $mails[$i];
}
usort($array, 'cmp');

$total = sizeof($mails);
$hostCounts = array();
$result = array();

for ($i = 0, reset($array); $i < $total
{
    $curr = current($array);
    if ($curr === false)
        $curr = reset($array);

    if (needPush($i, $total, $curr, $hostCount[key($array)]))
    {
        $result[] = current($curr);
        if (next($array[key($array)]) === false)
            array_splice($array, key($array), 1);
        $i++;
    }
    else
        next($array);

}
echo '<pre>';
print_r($result);
echo '</pre>';

UPD: пару слов все таки скажу тем, кто будет разбираться. Принцип строится на том, что каждый массив имеет свой указатель (итератор). То есть сбор массива получается просто грамотным передвижением указателей + обработкой текущего положения указателей (для определения, нужно ли добавлять адрес в конечный массив).

Спустя 54 секунды (7.08.2009 - 20:07) Krevedko написал(а):

разберемся. По крайней мере я постараюсь !

Спустя 2 часа, 33 минуты, 28 секунд (7.08.2009 - 22:41) Alchemist написал(а):

glock18, что-то у меня твой вариант не заработал...

PHP

$mails = array(
"john@one.net","alex@one.net","max@one.net","aa@one.net","bb@one.net",
"peret@two.com","mike@two.com","jack@two.com",
"mama@three.com","papa@three.com","sister@three.com","brother@three.com","unkle@three.com","aunt@three.com"
);

/*Результат: Array
(
    [0] => mama@three.com
    [1] => mama@three.com
    [2] => mama@three.com
    [3] => mama@three.com
    [4] => mama@three.com
    [5] => mama@three.com
    [6] => john@one.net
    [7] => john@one.net
    [8] => john@one.net
    [9] => john@one.net
    [10] => john@one.net
    [11] => peret@two.com
    [12] => peret@two.com
    [13] => peret@two.com
)
*/

Спустя 23 минуты, 1 секунда (7.08.2009 - 23:04) Alchemist написал(а):

добавлю уже разом и свой вариант:

PHP

$massiv = array();        // массив мыл

$tmp = array();
foreach($massiv as $email){
    list(,$a) = explode('@',$email);
    $tmp[$a][] = $email;
}
usort($tmp,create_function('$a,$b','return count($a) - count($b);'));

$a = array_shift($tmp);                // базовый массив: в нем будут распределяться остальные
while($b = array_shift($tmp)) {        // второй массив: он будет распределяться в первом
    $res = array();
    $cnt = 1;                        // начальное значение счетчика
    $ratio = count($a) / count($b);    // соотношение распределения

    while(count($b)){                 // пока в малом массиве остались элементы
        if ($cnt >= $ratio) {            // если значение счетчика больше соотношения
            $res[] = array_shift($b);    // распределяем очередной элемент
            $cnt -= $ratio;            // ...и уменьшаем счетчик
        } else {                        // в противном случае
            $res[] = array_shift($a);    // добавляем элемент базового массива
            $cnt += 1;                    // ...и увеличиваем счетчик
        }
    }
    $a = array_merge($res,$a); // добавляем оставшиеся элементы базового массива и перезаписываем его.
}

Спустя 27 минут, 35 секунд (7.08.2009 - 23:31) kirik написал(а):

Пошла оптимизация!

PHP

$tmp = array();
foreach($massiv as $email){
    list(,$a) = explode('@',$email);
    $tmp[$a][] = $email;
}

можно заменить на

PHP

for($tmp = array(); $e = each($massiv); $tmp[end(explode('@', $e[1]))][] = $e[1]);

Спустя 21 минута, 18 секунд (7.08.2009 - 23:53) glock18 написал(а):

Alchemist
Странно, что не заработал. У меня все пашет. Выложу файлом, мало ли что...

Спустя 31 минута, 43 секунды (8.08.2009 - 00:24) kirik написал(а):

Цитата (glock18 @ 7.08.2009 - 15:53)

Странно, что не заработал. У меня все пашет.

У меня тоже ОК!

Спустя 1 час, 11 минут, 31 секунда (8.08.2009 - 01:36) Alchemist написал(а):

http://www.selectisrael.com/emailSort.php

твой файл без единого изменения...

Спустя 25 минут, 2 секунды (8.08.2009 - 02:01) kirik написал(а):

Цитата (Alchemist @ 7.08.2009 - 17:36)

твой файл без единого изменения...

Чет не то.. Там должно идти первой строчкой чет типа

этого

Код

1 - 0.428571428571 0.5 - 0.357142857143 0.333333333333 - 0.214285714286 0.333333333333 - 0.428571428571 0.5 - 0.428571428571 0.25 - 0.357142857143 0.4 - 0.357142857143 0.2 - 0.214285714286 0.333333333333 - 0.214285714286 0.333333333333 - 0.428571428571 0.428571428571 - 0.428571428571 0.5 - 0.428571428571 0.25 - 0.357142857143 0.333333333333 - 0.357142857143 0.4 - 0.357142857143 0.2 - 0.214285714286 0.363636363636 - 0.428571428571 0.416666666667 - 0.428571428571 0.307692307692 - 0.428571428571 Array

Спустя 57 минут, 26 секунд (8.08.2009 - 02:58) Alchemist написал(а):

да я понимаю, что должно

я тоже вижу этот echo в коде

но нету, как вы сами видите...

Вобщем я покопался и нашел проблему: это строка

PHP

$curr = current($array);

Выглядит как будто при копировании итератор обнуляется. На сервере стоит PHP 5.2.1

Спустя 4 часа, 48 минут, 55 секунд (8.08.2009 - 07:47) glock18 написал(а):

Цитата (Alchemist @ 7.08.2009 - 23:58)

Выглядит как будто при копировании итератор обнуляется. На сервере стоит PHP 5.2.1

ммм... да нет. ничего не обнуляется там - не должно по крайней мере

. это же возврат текущего элемента просто, а не reset.

Насчет версии тоже че-т сумневаюсь. У меня 5.26, но эти указатели, по-моему, в пхп уже так давно, что... ))) что я затрудняюсь понять что за такая проблема там у тебя)))

В принципе этого же можно было добиться, если ввести всякие $i, $k для этих массивов, но со встроенными указателя мне несколько изящней показалось

Спустя 5 часов, 33 минуты, 18 секунд (8.08.2009 - 13:20) Alchemist написал(а):

блин, glock18, я знаю что такое итераторы ! и я знаю как давно они есть в пхп !

я пишу не о том что "я думаю" или "должно быть", а о том что фактически происходит. Я вставил два echo в твой код

Цитата

$curr = current($array); echo key($curr);
...
if (next($array[key($array)]) === false)
array_splice($array, key($array), 1);
echo key($array[key($array)]);

и если второй идет по массиву как и задумано, то первый всегда 0.

Поэтому я и написал, про обнуление итератора.

Update: Блин, ну вы и писатели... полдня угробил чтобы найти объяснение феномену
http://bugs.php.net/bug.php?id=41372 (Bug #41372 Internal pointer of source array resets during array copying )

Пофиксено только в версии 5.2.4

Спустя 2 часа, 25 минут, 32 секунды (8.08.2009 - 15:46) Sylex написал(а):

Alchemist
бугага, да такое бывает, убиваешь пол дня на баг какой-нить дряный

Спустя 1 час, 25 минут, 48 секунд (8.08.2009 - 17:12) glock18 написал(а):

Alchemist
приношу извинения

Быстрый ответ:

Здесь расположена полная версия этой страницы.