За последние 24 часа нас посетили 22746 программистов и 1259 роботов. Сейчас ищут 706 программистов ...

усовершенствование алгоритма)

Тема в разделе "Решения, алгоритмы", создана пользователем bombascter, 24 янв 2012.

  1. bombascter

    bombascter Активный пользователь

    С нами с:
    24 янв 2012
    Сообщения:
    2
    Симпатии:
    0
    Всем доброе утро! У меня друг - логопед, ему нужна программа, которая находила слова различающиеся только одной буквой. Я решил ему помочь)
    Вот код:
    Код (Text):
    1. <?php
    2. $startTime = date("s");
    3. $numfor = 0;
    4. $file = 'db.txt';
    5. $files = fopen($file,'r');
    6. $buffer = fgets($files, 6000);
    7. $global = array();
    8. $db = $buffer;
    9. $array = explode(" ",$db);
    10. $alfavit = array("а","б","в","г","д","е","ж","з","и","й","к","л","м","н","о","п","р","с","т","у","ф","х","ц","ч","ш","щ","ъ","ы","ь","э","ю","я");
    11. for($i = 0; $array[$i]; $i++){
    12.     $numfor++;
    13.     $slovoArray = array();
    14.     $slovo = "";
    15.     for($d = 0;$string = mb_substr($array[$i], $d, 1, 'UTF-8');$d++){
    16.         array_push($slovoArray,$string);
    17.         $slovo .= $string;
    18.     }
    19.     for($c = 0; $slovoArray[$c]; $c++){ // пока есть буквы в слове
    20.         $original = $slovoArray[$c];
    21.         for($j = 0; $alfavit[$j]; $j++){ // пока есть буквы в алфавите
    22.             $numfor++;
    23.             $slovoArray[$c] = $alfavit[$j];
    24.             $read = implode("", $slovoArray); //нашел эту функцию и убрал ниже стоячий код, но эта функция работает не быстро как я думал...
    25.             //for($r =0; $slovoArray[$r]; $r++){ // формируем новое изменненое слово
    26.             //  $numfor++;
    27.             //  $read .= $slovoArray[$r];
    28.             //}
    29.             if(array_search($read,$array) !== false && $slovo != $read){
    30.                     if(!is_array($global[$slovo])){
    31.                         $global[$slovo] = array();
    32.                         array_push($global[$slovo],$read);
    33.                     }else{
    34.                         array_push($global[$slovo],$read);
    35.                     }
    36.                     //echo "<b style='color:red'>".$slovo.":".$read."</b></br>";
    37.             }else{
    38.                     //echo $read."</br>";
    39.             }
    40.             $read = "";
    41.             $slovoArray[$c] = $original;
    42.         }
    43.     }
    44. }
    45. $endtTime = date("s");
    46. echo "<h2>start time : ".$startTime.", endtime = $endtTime</h2>";
    47. echo "<pre>";
    48. print_r($global);
    49. echo "</pre>";
    50. echo "<h1>количество операций: $numfor, кол. слов в массиве = ".count($array)."</h1>";
    51. ?>
    Дело в том что эта функция ест очень много ресурсов, и больше чем 1000 слов посчитать не может (думает более 30 с.). Подскажите, кто знает как бы ее усовершенствовать, что-бы не ела так много ресурсов? Заранее всем огромное спасибо!
     
  2. 440Hz

    440Hz Старожил
    Команда форума Модератор

    С нами с:
    21 дек 2012
    Сообщения:
    8.003
    Симпатии:
    1
    Адрес:
    Оттуда
    т.е. надо пробежаться по массиву n^n раз?
     
  3. asokol

    asokol Активный пользователь

    С нами с:
    17 янв 2012
    Сообщения:
    162
    Симпатии:
    0
    Попробуйте сравнивать слова побуквенно. Мне кажется, это должно быть быстрее. К тому же, как Вы понимаете, сравнивать можно до 2 несовпадений и только с последующими словами, которые по длине отличаются не больше, чем на 1 символ.
     
  4. Gromo

    Gromo Активный пользователь

    С нами с:
    24 май 2010
    Сообщения:
    2.786
    Симпатии:
    2
    Адрес:
    Ташкент
    1. http://php.net/manual/ru/function.set-time-limit.html
    2. найди алгоритм пузырьковой сортировки для примера сравнения каждого слова с другими - данный алгоритм отлично подходит для последовательного перебора всех слов в списке без повторений
    3. отсортируй слова по алфавиту и кол-ву букв перед началом поиска, тогда сможешь прервать поиск на первом слове, чья длина будет больше на 2 буквы
    4. продумай алгоритм сравнения двух слов - вариантов море.
     
  5. igordata

    igordata Суперстар
    Команда форума Модератор

    С нами с:
    18 мар 2010
    Сообщения:
    32.410
    Симпатии:
    1.768
    я может не вчитывался, но как вы собираетесь делать слова из алфавита?
     
  6. Volt(220)

    Volt(220) Активный пользователь

    С нами с:
    11 июн 2009
    Сообщения:
    1.640
    Симпатии:
    1