• ,

level07.lesson09.task04 У кого быстрее алгоритм работает? Конкурс.

Интересно, полагаю, будет посмотреть на самые быстродействующие алгоритмы решения этой задачи. Естественно, что число записей в списке должно быть таким, чтобы время выполнения программы на компьютере можно было бы легко вычислить. Так создадим единый список из ста тысяч строк и сравним время выполнения…

N.B.!
1. Согласно пункту 2.2. предложенной задачи: «удваивать все слова содержащие букву «л».», для единообразия станем так:

На входе:
роза
лира
лоза
ложка
коза
кора
коралл
сорока
носорог
финал

На выходе:
лира
лоза
лоза
ложка
ложка
коза
коралл
финал
финал


2. Список один и тот же, и хотя он формируется путем десяти тысячекратного повторения из десяти строк, считаем его случайным.
3. Срок самостоятельной публикации конкурсных вариантов решения этой задачи истекает 5 февраля 2017 года в 12 часов дня (время московское).
4. Каждый участник форума может самостоятельно оценить быстродействие предложенных вариантов на своем компьютере и поставить «плюсик» тому, кого он считает победителем в этом конкурсе."


/*
ТЕКСТ КОНКУРСНОЙ ЗАДАЧИ СО ВСЕМИ КОРРЕКТИРОВКАМИ ИСХОДНОЙ ЗАДАЧИ level07.lesson09.task04:
*/


/*

2. Метод fix должен:
2.1. удалять из списка строк все слова, содержащие букву «р»
2.2. удваивать все слова содержащие букву «л».
2.3. если слово содержит и букву «р» и букву «л», то оставить это слово без изменений.
2.4. с другими словами ничего не делать.
Пример:
роза
лира
лоза
ложка
коза
кора
коралл
сорока
носорог
финал
...
Выходные данные:
лира
лоза
лоза
ложка
ложка
коза
коралл
финал
финал
...
*/



import java.util.ArrayList;

public class ManipulationsWithTheList {

    public static void main(String[] args) throws Exception
    {
        long startTime = System.currentTimeMillis();

        ArrayList<String> list = new ArrayList<String>();

        for (int i = 0; i < 10000 ; i++) {
            list.add("роза");
            list.add("лира");
            list.add("лоза");
            list.add("ложка");
            list.add("коза");
            list.add("кора");
            list.add("коралл");
            list.add("сорока");
            list.add("носорог");
            list.add("финал");
        }

        list = fix(list);

        for (String s : list)
        {
            System.out.println(s);
        }

        long timeSpent = System.currentTimeMillis() - startTime;

        System.out.println("Эта программа выполнялась " + timeSpent + " миллисекунд.");
    }

    public static ArrayList<String> fix(ArrayList<String> list)
    {
        //напишите тут ваш код

    }
}


Дополнение от 31.01.2017
Уважаемые коллеги!
Настоятельно прошу еще раз ознакомиться со всеми условиями конкурсной задачи. Особо отмечу следующее:
на входе упорядоченная коллекция строк;
на выходе также должна быть упорядоченная коллекция строк (вывод её в консоль используется исключительно для визуального подтверждения верности произведенных манипуляций с исходной псевдослучайной коллекцией);
— сколько времени выполнялся метод fix, просьба, вывести в консоль дополнительно.

Ссылки на все конечные полные тексты программ участвующих в конкурсе будут находиться в самом первом сообщении темы. Просьба к участникам опубликовать их в своих сообщениях с пометкой: «НА КОНКУРС», чтобы я смог бы их собрать вместе и опубликовать.

Конкурсанты:
Torin текст программы содержит отклонения от конкурсной задачи
JuriMik текст программы
Javin текст программы
Himeg текст программы
Тестирование

Проводилось на:
Intel Core i7-2600 CPU @ 3.4 GHz x 4, RAM 16 GB

Windows 7 professional x64
JRE 1.8.0_121
IDE Eclipse Java EE IDE for Web Developers. Version: Neon.1a Release (4.6.1)

Linux Mint 17 Cinnamon 64-bit (v. 2.2.16) 3.13.0-24-generic
JRE 1.8.0_25
IDE Eclipse Java EE IDE for Web Developers. Version: Neon.2 Release (4.6.2)

Средние арифметические значения времени выполнения метода fix (в миллисекундах) подсчитывались по десяти попыткам:

60 комментариев

Archie369
Быстрее всего будет работать с массивами вместо коллекций.
Javin
Только реализовать решение этой задачи через такое эффективное использование массивов мне не под силу. Если сможете, то можно будет сравнить результаты по быстродействию и потребностям в использовании оперативной памяти. Сейчас же, без использования массивов, получил рекордное время выполнения этой задачи на моем весьма старом компьютере с Линуксом в 0,776 секунд. Просто ошеломлен быстродействием java-машины в этих сложных манипуляциях с упорядоченной коллекцией в сто тысяч строк. Ведь предполагал сперва, что время выполнения задачи будет несколько секунд, или, даже, десятков секунд… Ай да Java, ай да чудо! Пытаюсь сейчас внести изменения в алгоритм программы, чтобы ещё быстрее всё выполнялось.
Archie369
На моем i3-3110m @ 2.4ghz результат 896мс. Попробуйте на вашем пк.
public class Main {

    public static void main(String[] args) throws Exception {

        long startTime = System.currentTimeMillis();

        String[] words = {
                "роза",
                "лира",
                "лоза",
                "ложка",
                "коза",
                "кора",
                "коралл",
                "сорока",
                "носорог",
                "финал",
        };

        String[] wordArray = new String[100000];

        for (int i = 0; i < wordArray.length; i+=words.length){
            for (int j = 0; j < words.length; j++){
                wordArray[i+j]=words[j];
            }
        }

        String[] res = fix(wordArray);



        for (int i = 0; i < res.length; i++){
            System.out.println(res[i]);
        }

        long timeSpent = System.currentTimeMillis() - startTime;
        System.out.println("Эта программа выполнялась " + timeSpent + " миллисекунд.");

    }


        public static String[] fix (String[] arr){
            String[] resultArray = new String[arr.length*2];
            int j = 0;
            for (int i = 0; i< arr.length; i++){
                if (arr[i].contains("л") && arr[i].contains("р") || !arr[i].contains("л") && !arr[i].contains("р")){
                    resultArray[j++] = arr[i];
                } else if (arr[i].contains("л") && !arr[i].contains("р")) {
                   resultArray[j++] = arr[i];
                    resultArray[j++] = arr[i];
                }
            }
            String[] trimmedResult = new String[j];

            for (int i = 0; i < trimmedResult.length; i++){
                trimmedResult[i] = resultArray[i];
            }
            return trimmedResult;
        }
Javin
260
321
348
247
256
270
319
225
251
273
277 — среднее арифметическое время выполнения этой программы на моем компьютере. (348-225)* 100%/225 = 54,7% разница между минимальным и максимальным временем выполнения этой программы. Не многоват ли такой перепад в быстродействии программы? Без использования массивов же перепад во времени выполнения программы у меня не превышает 25%.
Archie369
Просто вывод слов по условию: 846мс на моем пк
public class Main {
    public static void main(String[] args) throws Exception {
        long startTime = System.currentTimeMillis();
        String[] words = {
                "роза",
                "лира",
                "лоза",
                "ложка",
                "коза",
                "кора",
                "коралл",
                "сорока",
                "носорог",
                "финал",
        };
        for (int i = 0; i < 10000; i++){
            for (int j = 0; j < words.length; j++){
                if (words[j].contains("р") && words[j].contains("л") || !words[j].contains("р") && !words[j].contains("л")){
                    System.out.println(words[j]);
                } else if (words[j].contains("л") && !words[j].contains("р")){
                    System.out.println(words[j]);
                    System.out.println(words[j]);
                }
            }
        }
        long timeSpent = System.currentTimeMillis() - startTime;
        System.out.println("Эта программа выполнялась " + timeSpent + " миллисекунд.");
    }
}
Javin
240
263
332
360
344
346
242
327
343
274
307,1 — ср. арифм.
Torin
Секундочку.

У кого быстрее алгоритм работает?

Так что мы измеряем, алгоритм или вывод в консоль? Зачем вы в своих решениях считаете вывод в консоль?
Берем для примера код Javin:

long st = System.currentTimeMillis();
list = fix(list);
long delta = System.currentTimeMillis() - st;


Вот и все что на самом деле важно.
Torin
private ArrayList<String> lines = new ArrayList<>();
    
    {
        for(int i = 0; i < 10000; i++) {
            lines.add("роза");
            lines.add("лира");
            lines.add("лоза");
            lines.add("ложка");
            lines.add("коза");
            lines.add("кора");
            lines.add("коралл");
            lines.add("сорока");
            lines.add("носорог");
            lines.add("финал");
        }
        
    }

public void todo(){
        long st = System.currentTimeMillis();
        fix(lines);
        long delta = System.currentTimeMillis() - st;
        System.out.println(delta + " мс");
        for (int i = 0; i < 20; i++) {
            System.out.println(lines.get(i));
        }
         System.out.println("Size: " + lines.size());
    }
    
    private void fix(ArrayList<String> as) {
        ArrayList<String> s = new ArrayList<>();
        for (String w : as) {
            if (w != null && w.contains("р") && !w.contains("л")) {
                continue;
            }
            
            if (w != null && w.contains("л") && !w.contains("р")) {
                s.add(w);                
            }
            s.add(w);
        }        
        lines = s;
    }


20 мс
core i5-6200U @ 2.30 GHz 2.40GHz
8 ГБ ОЗУ
Archie369
for (int i = 0; i < 20; i++) {
это зачем?
Torin
выводит 20 строк из листа в консоль, чтобы увидеть что нет лажи. Можно конечно и убрать, но я люблю наглядность
Javin
Torin, было бы удобней, полагаю, чтобы листинг программы был бы полным, как у Archie369, или Himeg. Чтобы его было бы проще запустить на выполнение таким как я новичкам.
Javin
Замечание справедливое и с благодарностью принимается.
Archie369
60мс
public class Main {

            public static void main(String[] args) throws Exception {
                    String[] words = {"роза", "лира", "лоза", "ложка", "коза", "кора", "коралл", "сорока", "носорог", "финал",};
                    String[] wordArray = new String[100000];
                    for (int i = 0; i < wordArray.length; i+=words.length){
                            for (int j = 0; j < words.length; j++){
                                    wordArray[i+j]=words[j];
                                }
                        }
                long startTime = System.currentTimeMillis();
                    String[] res = fix(wordArray);
                long timeSpent = System.currentTimeMillis() - startTime;
                    for (int i = 0; i < res.length; i++){
                            System.out.println(res[i]);
                        }
                    System.out.println("Эта программа выполнялась " + timeSpent + " миллисекунд.");
                }
                public static String[] fix (String[] arr){
                        String[] resultArray = new String[arr.length*2];
                        int j = 0;
                        for (int i = 0; i< arr.length; i++){
                                if (arr[i].contains("л") && arr[i].contains("р") || !arr[i].contains("л") && !arr[i].contains("р")){
                                        resultArray[j++] = arr[i];
                                    } else if (arr[i].contains("л") && !arr[i].contains("р")) {
                                       resultArray[j++] = arr[i];
                                        resultArray[j++] = arr[i];
                                    }
                            }
                        String[] trimmedResult = new String[j];
                        for (int i = 0; i < trimmedResult.length; i++){
                                trimmedResult[i] = resultArray[i];
                            }
                        return trimmedResult;
                    }
}
Javin
На моём компьютере с Линуксом эта программа, Archie369, выполнялась (в миллисекундах):
20
18
18
17
21
20
18
21
18
20
19,1 — ср. арифм.
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-01-30 01:52:19 пользователем Torin
Этот код на моей машине выдал от 16 до 31 мс. Но можно лучше.

    public static String[] lines = new String[100000];
    public static String[] words = {"роза", "лира", "лоза", "ложка", "коза", "кора", "коралл", "сорока", "носорог", "финал"};
    static{
        for(int i = 0; i < 10000; i += words.length) {
            for (int in = 0; in < words.length; in++) {
                lines[i + in] = words[in];
            }
        }        
    }
    
    public static void todo(){
        long st = System.currentTimeMillis();
        fix();
        long delta = System.currentTimeMillis() - st;
        System.out.println(delta + " мс");
        for (int i = 0; i < 20; i++) {
            System.out.println(lines[i]);
        }
       
    }
    
    public static void fix() {
        String[] s = new String[200000];
        int i = 0;
        for (String w : lines) {
            if (w != null && w.contains("р") && !w.contains("л")) {
                continue;
            }
            
            if (w != null && w.contains("л") && !w.contains("р")) {
                s[i++] = w;                
            }
            s[i++] = w;
        }        
        lines = s;
    }



0 — 10 мс.
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-01-30 02:16:52 пользователем Torin
15-25 мс 1 млн строк

static int i = 0;
    static String[] s =              new String[2000000]; // (!)
    public static String[] lines =   new String[1000000]; // (!)
    public static String[] words = {"роза", "лира", "лоза", "ложка", "коза", "кора", "коралл", "сорока", "носорог", "финал"};
    static{
        for(int i = 0; i < 100000; i += words.length) {
            for (int in = 0; in < words.length; in++) {
                lines[i + in] = words[in];
            }
        }        
    }
    
    public static final void todo(){
        long st = System.currentTimeMillis();
        fix();
        long delta = System.currentTimeMillis() - st;
        System.out.println(delta + " мс");
        for (int i = 0; i < 20; i++) {
            System.out.println(lines[i]);
        }       
    }
    
    public static void fix() {       
        for (String w : lines) {
            if (w != null && w.contains("р") && !w.contains("л")) {
                continue;
            }           
            if (w != null && w.contains("л") && !w.contains("р")) {
                s[i++] = w;                
            }
            s[i++] = w;
        }        
        lines = s;
    }
Archie369
У вас остается массив наполовину пустой, я бы его сократил чтобы максимально соответствовать требованиям задачи.
Torin
Обычные массивы в джаве не обрезаются, для этих целей нужно использовать ArrayList. Но ArrayList на миллионе элементов пересоздает свой внутренний массив неколько раз, и это может сказаться на скорости (хоть и не значительно). Для того чтобы решить эту задачу для валидатора достаточно самого тривиального решения. Но мы же хотим ускорить задачу максимально? тут валидатор мое решение уже не схавает, это точно.
Himeg
С помощью ArrayList + Array в методе fix:
import java.io.PrintWriter;
import java.util.ArrayList;

public class ManipulationsWithTheList
{

    public static void main(String[] args) throws Exception
    {
        long startTime = System.currentTimeMillis();

        ArrayList<String> list = new ArrayList<>();
        String[] pattern = {"роза", "лира", "лоза", "ложка", "коза", "кора", "коралл", "сорока", "носорог", "финал"};

        for (int i = 0; i < 10000; i = i + pattern.length)
        {
            for (int j = 0; j < pattern.length; j = j + 1)
            {
                list.add(pattern[j]);
            }
        }

        PrintWriter out = new PrintWriter(System.out, false);

        long T = System.currentTimeMillis();
        list = fix(list);
        T = System.currentTimeMillis()-T;

        for (int i = 0; i < list.size(); i = i + 1)
        {
            out.println(list.get(i));
        }

        out.println("Метод fix выполнялся " + T + " миллисекунд.");
        startTime = System.currentTimeMillis() - startTime;
        out.println("Эта программа выполнялась " + startTime + " миллисекунд.");

        out.flush();
    }

    public static ArrayList<String> fix(ArrayList<String> list)
    {
        ArrayList<String> result = new ArrayList<>(list.size());
        String[] arr = list.toArray(new String[list.size()]);
        int r, l;
        for (String s : arr)
        {
            r = s.indexOf('р');
            l = s.indexOf('л');
            if (r > -1 && l == -1)
            {
                continue;
            }
            if (r == -1 && l > -1)
            {
                result.add(s);
            }
            result.add(s);
        }
        return result;
    }
}


Метод fix на I7-3632QM 2,2 GHz 8 Gb RAM выполняется за 2-4 мс, а вся задача, включая вывод в консоль, за ~50 мс.
При размере листа в 1000000 метод fix 12-16 мс, вся задача 130-140 мс.
В варианте «всё на массивах» цифры те же, поэтому постить не буду.
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-01-30 11:00:21 пользователем Torin
Согласен. Теперь жалею что поленился сам переписать на indexOf, хотя даже сидел искал его в исходниках, он оказался действительно быстрее contains. Я заменил в своем последнем варианте на indexOf, результат на моей машине стабильнее 10-13 мс. Твой же код иногда стреляет быстрее, но разброс больше 9 -17 мс. Я думаю дело в том что я сделал статичным абсолютно ВСЕ. В любом случае, вариантов как это ускорить еще больше, я не вижу.
Archie369
можно попробовать еще по каждой строчке получить последовательность байт getBytes()
и в цикле проверить соответствие байт буквы р, л на наличие этих байт в полученном массиве байт слова.
Torin
Вот для этого я и пытался найти исходник indexOf, чтобы понять, каким именно образом он ищет вхождение. Сам хотел попробовать вложенные циклы (можно банально на charAt(i) проверить), но вложенный цикл сильно замедлит работу — инфа 100%, можно конечно попробовать, ради интереса
Himeg
  • Himeg
  • +1
  • Комментарий отредактирован 2017-01-30 12:48:57 пользователем Himeg
indexOf() тоже использует цикл. По идее, вложенный цикл не должен замедлить работу, если написать его так же, как реализовано внутри indexOf() (но тогда теряется смысл). У меня был промежуточный вариант с хитрым и медленным вложенным циклом, на который я в итоге забил))

UPD мне понравилась идея не дергать метод объекта, я вставил вместо indexOf() циклы из реализации метода indexOf и время fix улучшилось процентов на 10 (максимум 14 мс на моей машине с миллионом строк):

            //r = s.indexOf('р');
            //l = s.indexOf('л');
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == 'р') {
                    r = i;
                    break;
                }
            }
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == 'л') {
                    l = i;
                    break;
                }
            }
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-01-30 11:58:27 пользователем Torin
public int indexOf(int ch, int fromIndex) {
        final int max = value.length;
        if (fromIndex < 0) {
            fromIndex = 0;
        } else if (fromIndex >= max) {
            // Note: fromIndex might be near -1>>>1.
            return -1;
        }

        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            // handle most cases here (ch is a BMP code point or a
            // negative value (invalid code point))
            final char[] value = this.value;
            for (int i = fromIndex; i < max; i++) {
                if (value[i] == ch) {
                    return i;
                }
            }
            return -1;
        } else {
            return indexOfSupplementary(ch, fromIndex);
        }
    }


Как видим, использование своего цикла for может ускорить наш метод максимум на пару процентов просто за счет того. что не будет дергаться метод объекта, а вся проверка будет пробегать непосредственно в цикле в нашем методе
Javin
Himeg, под Линуксом эта программа выдала:
Метод fix выполнялся:
2
3
2
2
3
2
1
3
4
3
2,5 — ср. арифм.
Эта программа выполнялась:

14
12
11
12
10
10
11
13
14
13
12 — ср. арифм.
Himeg
Вообще, тема очень интересная! Не могу не поставить плюсик топикстартеру)))
Torin
Согласен, тоже поставлю плюс топикстартеру. Он заставил меня крепко позадротить. Я очень люблю тему производительности, особенно когда кто-то бросает вызов. Кстати о:

static int i = 0;
    static boolean r;
    static boolean l;    
    static ArrayList<char[]> lines = new ArrayList<>();
    static ArrayList<char[]> s = new ArrayList<>();
    public static char[][] words = {"роза".toCharArray(), "лира".toCharArray(), "лоза".toCharArray(), "ложка".toCharArray(),
                                    "коза".toCharArray(), "кора".toCharArray(), "коралл".toCharArray(),
                                    "сорока".toCharArray(), "носорог".toCharArray(), "финал".toCharArray()};
    static{
        for(int i = 0; i < 100000; i += words.length - 1) {
            for (int in = 0; in < words.length; in++) {
                lines.add(words[in]);
            }
        }        
    }
    
    public static final void todo(){
        long st = System.currentTimeMillis();
        fix();
        long delta = System.currentTimeMillis() - st;
        System.out.println(delta + " мс");
        for (int i = 0; i < 20; i++) {
            for (int kk = 0; kk < lines.get(i).length; kk++) {
                System.out.print(lines.get(i)[kk]);
            }
            System.out.println();
        }       
    }
    
    public static void fix() {            
        for (char[] temp : lines) {            
            int len = temp.length;
            for (int x = 0; x < len; x++) {
                r = !r ? temp[x] == 'р' : r;
                l = !l ? temp[x] == 'л' : l;                
            }
            if (r && !l) {
                continue;
            } else if (l && !r) {
                s.add(temp);
            }
            s.add(temp);
            r = false;
            l = false;            
        }        
        lines = s;
    }


10 мс на 1 млн элементов. Вот теперь я точно не знаю как еще ускорить.
Himeg
Нет, ну погоди, так нельзя)) Ладно, черт с ним, что потом эта экономия компенсируется затратами на склеивание при печати. Ты выполнил предварительное преобразование каждого элемента повторяющейся группы в массив символов, а если будет 100000 случайных строк? С таким же успехом можно было и r, l сразу предвычислить там же, где у тебя преобразование в chararray, а в fix пользоваться уже готовыми boolean значениями.
Torin
Да, я понимаю к чему ты ) но вопрос звучал на скорость алгоритма в методе fix. Это значит что ради этого я готов на все, вплоть до:

fix() {
    lines = s;
}


Я думаю вряд ли можно придумать что-то эффективнее )) Но если серьезно:

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

Тогда:

String[] words = {"нужные","нам","слова","из","условия"};
ArrayList<String> whatEverWords = new ArrayList<>();
int newSize = new Random().nextInt(2000000) + 10000;
for (int i = 0; i < newSize; i++) {
    whatEverWords.add(words[new Random().nextInt(words.length)]);
}

static {
    for (int x = 0; x < 100500; x++) {
        for (int xx = 0; xx < whatEverWords.size(); xx++) {
            lines.add(whatEverWords.get(xx).toCharArray());
        }
    }
}


Далее по аналогии. А вот

r, l сразу предвычислить там же, где у тебя преобразование в chararray


согласен, я довел эту мысль до абсурда в самом начале этого коммента :) Но насчет массива не совсем согласен. Ведь Стринга сама по себе и есть массив символов, но мы не имеем прямого доступа к нему, и он нам и не нужен, ибо это дольше. Фактически мы как бы изобретаем свою стрингу без лишних методов, зато с блек джеком и шл. Короче, это велосипед, вот и все :)
Himeg
Можно ещё абсурднее: последовательность из десяти слов обработать один раз, а потом результат 100k раз добавить в список (так как у нас 10 повторяющихся слов, то конкретика реализации их обработки уже не важна). Сделать всё это в методе main)))
Метод fix при этом будет выглядеть так:
fix() 
{
}

Ладно, думаю, что тут уже действительно ничего не ускорить. Для миллиона строк даже 20 мс уже можно считать отличной оптимизацией
Torin
согласен ))) после нашей работы старенький комп Javin'a который работает на линуксе, теперь от такой скорости просто начнет телепортироваться во времени
Javin
Буду ждать полный текст Вашей программы, дорогой Torin, чтобы насладиться ей до «телепортации» :)
Javin
Запускал вчера свой вариант программы с упорядоченной коллекцией в 100 тыс. строк (без использования в алгоритме массивов) в разных IDE c Linux Mint 17 Cinnamon 64-bit и Windows 7 Prof. 64- бит. Компьютер один и тот же, а результаты получились очень разные (считалось полное время работы программы, ведь с дельным замечанием уважаемого Торина по этому поводу я ещё не был знаком).

Linux
Eclipse: 799 ср. арифм.
NetBeans: 3072 ср. арифм.
IntelliJ IDEA: 909 ср. арифм.
из командной строки: 2887 ср. арифм.

Windows
Eclipse: 1757 ср. арифм.
из командной строки: 10200 ср. арифм.
Javin
Уважаемые коллеги!
Настоятельно прошу еще раз ознакомиться со всеми условиями конкурсной задачи. Особо отмечу следующее:
на входе упорядоченная коллекция строк;
на выходе также должна быть упорядоченная коллекция строк (вывод её в консоль используется исключительно для визуального подтверждения верности произведенных манипуляций с исходной псевдослучайной коллекцией);
— сколько времени выполнялся метод fix, просьба, вывести в консоль дополнительно.

Ссылки на все конечные полные тексты программ участвующих в конкурсе будут находиться в самом первом сообщении темы. Просьба к участникам опубликовать их в своих сообщениях с пометкой: «НА КОНКУРС», чтобы я смог бы их собрать вместе и опубликовать.
Javin
НА КОНКУРС

/**
 *
 * @author Javin
 */

import java.util.ArrayList;

public class ManipulationsWithTheList {

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();

        ArrayList<String> list = new ArrayList<String>();

        for (int i = 0; i < 10000; i++) {
            list.add("роза");
            list.add("лира");
            list.add("лоза");
            list.add("ложка");
            list.add("коза");
            list.add("кора");
            list.add("коралл");
            list.add("сорока");
            list.add("носорог");
            list.add("финал");
        }

        long startTimeFix = System.currentTimeMillis();

        fix(list);

        long timeSpentFix = System.currentTimeMillis();

        list.forEach(System.out::println);

        long timeSpent = System.currentTimeMillis();

        System.out.printf("\nФормирование исходной коллекции list:%5d мсек\n" +
                        "Продолжительноть работы метода fix:%7d мсек √\n" +
                        "Вывод результатов в консоль:%14d мсек\n" +
                        "ИТОГО:%36d мсек\n",
                startTimeFix - startTime, timeSpentFix - startTimeFix,
                timeSpent - timeSpentFix, timeSpent - startTime);

    }

    public static void fix(ArrayList<String> list) {
        int listSize = list.size(), isP, isL;

        for (int i = 0; i < listSize; i++) {

            isP = list.get(i).indexOf('р');
            isL = list.get(i).indexOf('л');

            if ((isP != -1) && (isL != -1)) {
                continue;// There are both 'р' and 'л'.
            }

            if (isP != -1) {
                list.remove(i);// There is 'р'.
                listSize--;
                i--;
                continue;
            }

            if (isL != -1) {
                list.add(i, list.get(i));// There is 'л'.
                listSize++;
                i++;
            }
        }
    }
}
Himeg
Ну если так, то ничего менять не буду, пусть однажды опубликованный код и будет НА КОНКУРС
JuriMik
  • JuriMik
  • +1
  • Комментарий отредактирован 2017-01-31 02:05:00 пользователем JuriMik
На конкурс
52-54 на моих дровах. Я так понимаю, у тебя комп побыстрее моей амд-шки будет. Протестируй, плиз.

import java.util.ArrayList;
import java.util.List;

public class Test {

	    public static void main(String[] args) throws Exception
	    {
	        List<String> list = new ArrayList<String>();

	        for (int i = 0; i < 10000 ; i++) {
	            list.add("роза");
	            list.add("лира");
	            list.add("лоза");
	            list.add("ложка");
	            list.add("коза");
	            list.add("кора");
	            list.add("коралл");
	            list.add("сорока");
	            list.add("носорог");
	            list.add("финал");
	        }
	        long startTime = System.currentTimeMillis();
	        list = fix(list);
	        long timeSpent = System.currentTimeMillis() - startTime;
	        for (String s : list)
	        {
	            System.out.println(s);
	        }

	        System.out.println(timeSpent);
	    }

	    public static List<String> fix(List<String> list)
	    {
	    	
	    	List<String> result = new ArrayList<>();
	    	for (String s : list) {
	    		if (s.indexOf('р') == -1) {
	    			if (s.indexOf('л') == -1) {
	    				continue;
	    			}
	    			else {
	    				result.add(s);
	    				result.add(s);
	    			}
	    		} else {
	    			if (s.indexOf('л') == -1) {
	    				continue;
	    			} else {
	    				result.add(s);
	    			}
	    		}
	    	}
	    	return result;
	    }

}
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-01-31 02:18:47 пользователем JuriMik
Проверил на
100000 — 77
1000000 — 2895. Тут можно оптимизировать работу ArrayList, но лень.

AMD A4-3300 2,50GHz, 8Gb, Win7 x64, Eclipse
Torin
AMD A4-3300 2,50GHz, 8Gb, Win7 x64, Eclipse

хм. Я может быть сейчас задам странный вопрос. А у тебя случайно не ноут асус с наклейками? ))
JuriMik
не асус, но с наклейками :-p
Они у меня потертости скрывают на корпусе
Torin
Прошлый мой нотик асус был с точно такими же характеристиками, и наклейки тоже скрывали потертости :) я его буквально весь обклеил виниловыми наклейками (покупал возле горбатого моста на шевченко). Хороший был нотик. Кстати если хочешь, у меня лежит А6 процессор новый в упаковочке для твоей материнки. Ноут продал а проц остался, так и лежит без дела
JuriMik
Не-не. Это параметры на десктопе. На ноуте у меня жена работает
Процессор интересно, напишу в скайп
JuriMik
Из командной строки на 100000
www.screencast.com/t/pSf4ofFejsl8
JuriMik
  • JuriMik
  • +1
  • Комментарий отредактирован 2017-01-31 02:35:38 пользователем JuriMik
Кстати, ложится код тоже очень просто.
Если в лист добавить вместо того, что было что-то типа:
list.add("офвфцфццфцфвцфвфцввцфвцфвцфвфцвффзал");
list.add("ифвцфвфвфццвцвцффвфвівфцвфцвффвфвал");
list.add("озфцфвфвфвфцвффвфвффвфуакукуааввфвфвфал");
list.add("ожфвфцфввцффффффффцввввввввввввввфвффкал");
list.add("козффцвццццццццццццццццццццццццццццццвфвфвфал");
list.add("кфвфвфффвфвфсуукукумукуаавфвфвфвоал");
list.add("кофвфвфвввввввввввввввввввввввввввввфвфалл");
list.add("софвфффффффффффффффффффффффффффффвфвфвфокал");
list.add("нофвфцццццццццйййййййййцуййцццццццфвфсоогл");
list.add("финфвцувввввввввввччччччччччччччччвфвфвфвал");
Тогда на 100000 строк уже отрабатывает более 150мс, а то и до 200мс.
Почему?
во-первых, indexOf обходит всю строку до конца (именно там стоит буква Л в строке), а не до первого встреченного символа.
во-вторых, отсутсвие буквы Р и присутствие Л заставляют добавлять строку дважды.
JuriMik
  • JuriMik
  • +2
  • Комментарий отредактирован 2017-01-31 02:37:36 пользователем JuriMik
Нафлудил, теперь можно и спать пойти :-D
А завтра могу свой конкурс запилить, у меня тоже есть интересная задачка на скорость и количество строк, хех.
Himeg
Неистово плюсую и жду конкурс! ))
Torin
Вот это я понимаю. Наконец на джаварашке начинается движняк! *достает свой плюсомет*
Javin
Результаты тестирования первых трёх программ-участников конкурса разместил в самом первом сообщении темы.
Torin
Подытожу, на конкурс — 1 000 000 элементов:
class Main {

    static int i = 0;
    static boolean r;
    static boolean l;    
    static ArrayList<char[]> lines = new ArrayList<>();
    public static char[][] words = {"роза".toCharArray(), "лира".toCharArray(), "лоза".toCharArray(), "ложка".toCharArray(),
                                    "коза".toCharArray(), "кора".toCharArray(), "коралл".toCharArray(),
                                    "сорока".toCharArray(), "носорог".toCharArray(), "финал".toCharArray()};
    static{
        for(int i = 0; i < 100000; i++) {
            for (int in = 0; in < words.length; in++) {
                lines.add(words[in]);
            }
        }
        System.out.println("Стартовая дерзость = " + String.format("%,d", lines.size()));
    }
    
    public static void main(String[] args) {
        long st = System.currentTimeMillis();
        fix(lines);
        long delta = System.currentTimeMillis() - st;
        for (int i = 0; i < 20; i++) {
            for (int kk = 0; kk < lines.get(i).length; kk++) {
                System.out.print(lines.get(i)[kk]);
            }
            System.out.println();
        }
        System.out.println("Анализ дерзости показал " + String.format("%,d", lines.size()) + " элементов тут.");
        System.out.println("Сколько тупили: " + delta + " мс");
    }
    
    public static void fix(ArrayList<char[]> lines) {
        ArrayList<char[]> s = new ArrayList<>();
        for (char[] temp : lines) {            
            int len = temp.length;
            r = false;
            l = false;   
            for (int x = 0; x < len; x++) {
                r = !r ? temp[x] == 'р' : r;
                l = !l ? temp[x] == 'л' : l; 
            }
            if (r && !l) {
                continue;
            } else if (l && !r) {
                s.add(temp);
            }
            s.add(temp);                     
        }        
        Main.lines = s;
    }
}


13 мс — 100 000 элементов
40 мс — 1 000 000 элементов

Core i5-6200U CPU @ 2.30 GHz 2.40 GHz

Himeg
  • Himeg
  • +2
  • Комментарий отредактирован 2017-01-31 23:58:01 пользователем Himeg
Уважаемые участники конкурса и организатор Javin!
Вынужден признать, что в моём конкурсном варианте, который я отметил как кандидата, наитупейший баг, в результате которого считается и выводится на печать в 10 раз меньше слов, чем я думал.
Понимая, что в любых соревнованиях такое автоматически засчитывается за дисквалификацию, я разозлился и, в качестве наказания себе самому, переписал практически весь код заново. В частности, добавил рекурсивный метод, который заполняет массив из 100000 элементов, изменил способ вывода в консоль и т.п. В результате получилось следующее:
<code>import java.io.BufferedWriter;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.nio.charset.Charset;
import java.util.ArrayDeque;

public class FinalManipulations
{
    public static void main(String[] args) throws Exception
    {
        long startTime = System.currentTimeMillis();

        String[] pattern = {"роза", "лира", "лоза", "ложка", "коза", "кора", "коралл", "сорока", "носорог", "финал"};
        String[] array = new String[pattern.length*10000]; //pattern.length times 10, or total amount of words

        long fillTime = System.currentTimeMillis();
        array = fill(array, pattern, 0, array.length/10);
        fillTime = System.currentTimeMillis() - fillTime;

        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new
                FileOutputStream(java.io.FileDescriptor.out), Charset.defaultCharset()), 1000000);

        long fixTime = System.currentTimeMillis();
        ArrayDeque<String> list = fix(array);
        fixTime = System.currentTimeMillis()-fixTime;

        long printTime = System.currentTimeMillis();
        for (String s : list)
        {
            out.write(s);
            out.newLine();
        }
        printTime = System.currentTimeMillis() - printTime;

        out.write("Метод fill (заполнение коллекции) выполнялся " + fillTime + " миллисекунд.");
        out.newLine();
        out.write("Метод fix выполнялся " + fixTime + " миллисекунд.");
        out.newLine();
        out.write("Вывод в консоль выполнялся " + printTime + " миллисекунд.");
        out.newLine();
        startTime = System.currentTimeMillis() - startTime;
        out.write("Вся программа выполнялась " + startTime + " миллисекунд.");
        out.newLine();

        out.flush();
    }

    public static ArrayDeque<String> fix(String[] array)
    {
        ArrayDeque<String> result = new ArrayDeque<>(array.length);
        int r, l;
        char ch;
        for (String s : array)
        {
            //r = s.indexOf("р");
            //l = s.indexOf("л");
            r = -1;
            l = -1;
            for (int i = 0; i < s.length(); i++)
            {
                ch = s.charAt(i);
                if (r == -1 && ch == 'р')
                {
                    r = i;
                    continue;
                }
                if (l == -1 && ch == 'л')
                {
                    l = i;
                }
            }
            if (r > -1 && l == -1)
            {
                continue;
            }
            if (r == -1 && l > -1)
            {
                result.add(s);
            }
            result.add(s);
        }
        return result;
    }

    public static String[] fill (String[] result, String[] fixedPattern, int start, int count)
    {
        int length = fixedPattern.length;
        if ((count - start)==1)
        {
            System.arraycopy(fixedPattern,0,result, start*length, length);
            return result;
        }
        int index = (int) (Math.log(count-start)/Math.log(2));
        int startNext = (int) Math.pow(2, index) + start;

        System.arraycopy(fixedPattern,0,result, start*length, length);

        for (int i = 0; i < index; i = i + 1)
        {
            System.arraycopy(result, start*length, result, start*length + (int)Math.pow(2, i)*length, (int)Math.pow(2, i)*length);
        }
        if ((startNext != count))
        {
            return fill(result, fixedPattern, startNext, count);
        }
        return result;
    }
}</code>
И со следующими результатами (I7 8GB Win10 IDE IntelliJ IDEA):
<code>Метод fill (заполнение коллекции) выполнялся 0 миллисекунд.
Метод fix выполнялся 11 миллисекунд.
Вывод в консоль выполнялся 24 миллисекунд.
Вся программа выполнялась 36 миллисекунд.</code>
Что с этим делать — на усмотрение организатора. Либо НА КОНКУРС, либо выкинуть меня из участников, заминусовав — я всё пойму)) Ещё раз спасибо Javin за хорошую тему для обсуждения.

PS вместо для миллиона слов:
Метод fill (заполнение коллекции) выполнялся 1 миллисекунд.
Метод fix выполнялся 35 миллисекунд.
Вывод в консоль выполнялся 775 миллисекунд.
Вся программа выполнялась 814 миллисекунд.
Torin
Либо НА КОНКУРС, либо выкинуть меня из участников, заминусовав — я всё пойму))

Ой да я тебя умоляю, может еще на кресте распять? :D Красавчик что сам сказал! :)
Javin
Теперь только 5-го февраля после 12 часов по моск. вр. собираюсь размещать в первом посте темы ссылки на тексты программ конкурсантов и результаты их запуска на моем PC. А вдруг кто-то из участников ещё внесёт изменения в свои программы, или устранит мелкие шероховатости типа: 0 + 11 + 24 = 36 ?!
Himeg
А ты думаешь 0+11+24=36 это шероховатость?)) Значения выводятся в консоль в округленном виде. Фактически это может быть 0.4 + 11.3 + 24.4 = 36.1
Javin
Предпочёл бы видеть 1 + 11 + 24 = 36, но о вкусах не спорят, уважаемый Himeg. «Что русскому хорошо, то немцу — смерть.» :)
Himeg
Ээмм… Дело даже не столько в округлении, сколько в том, что Время выполнения всей программы совершенно не равно сумме времени выполнения трех методов. Создание переменных String[], создание объекта BufferedWriter и т.п. — учитывается в общем времени выполнения программы, но ни в одном из времени выполнения методов.
Javin
Волшебное слово: «менее» перед единицей, думаю, придало бы недостающий шарм для наблюдателей, непосвященных во все тонкости программистского искусства. Но не спорю, Вам как автору виднее.
Himeg
Javin, ок, приму к сведению!)
Javin
Конкурс завершен. Общие сведения о нем в первом сообщении этой темы.
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-05 21:09:40 пользователем Torin
Так а кто победил? кто самый быстрый Гонзалес?

Himeg?
Javin
Получается, что именно у Himegа самый быстрый код. Его решение с промежуточным использованием массива оказалось процентов на 10% шустрее, чем вариант через использование дополнительной коллекции у JuriMikа. Ну, а непосредственные удаления и вставки элементов в коллекцию, что использовал я, уж больно продолжительны по сравнению с этими двумя вариантами.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.