D vs C++ - Священные войны - Страница 34

@nullxdth · 06.03.2015, 22:00

Студворк — интернет-сервис помощи студентам

Dennis Ritchie, у меня есть подозрения, что ты нас обманываешь. Ты, похоже, не олимпиадник. Ты или школьник или первокурсник заборостроительного. Зачем ты вычисляешь каждый раз размер слов, с такими-то входными ограничениями на длину слов, будет достаточно долго.

Добавлено через 55 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun f ()
  (flet ((read&split ()
           (cl-ppcre:split "\\s+" (read-line))))
    (let ((table (make-hash-table :test #'equal)))
      (destructuring-bind (n m &aux (m (parse-integer m))) (read&split)
        (declare (ignore n))
        (dotimes (i m)
          (destructuring-bind (a b) (read&split)
            (setf (gethash a table) (if (> (length a)
                                           (length b))
                                        b
                                        a)))))
      (format t "~{~a~^ ~}" (mapcar (alexandria:rcurry #'gethash table)
                                    (read&split))))))

@Dennis Ritchie · 06.03.2015, 22:12 **[ТС]**

Сообщение от nullxdth

с такими-то входными ограничениями на длину слов, будет достаточно долго.

15 мс, по-вашему, долго?

Сообщение от nullxdth

Зачем ты вычисляешь каждый раз размер слов

А как ещё это сделать в императивном стиле?

Сообщение от nullxdth

Ты или школьник или первокурсник заборостроительного.

Ну тогда вас обманывает школьник или первокурсник заборостроительного.

@nullxdth · 06.03.2015, 22:32

Сообщение от Dennis Ritchie

А как ещё это сделать в императивном стиле?

Причём тут императивный стиль... Приведенное решение на CL императивно чуть менее чем на 142%. Кто мешает в таблицу по значению записывать меньшую по размеру строку и, далее, отобразить набор слов на эту таблицу 1 в 1?

Добавлено через 11 минут

Сообщение от Dennis Ritchie

15 мс, по-вашему, долго?

Лол. На каких входных данных? Надеюсь не на тех, которые в примере

Если так, то 15мс - это бесконечность.

@castorsky · 06.03.2015, 22:34

Сообщение от nullxdth

чуть менее чем на 142%

146 же

Добавлено через 57 секунд

Сообщение от Dennis Ritchie

15 мс, по-вашему, долго?

хм... курить матчасть чтоле.

@Dennis Ritchie · 06.03.2015, 22:58 **[ТС]**

Сообщение от nullxdth

На каких входных данных?

На максимальных.

Сообщение от nullxdth

Приведенное решение на CL императивно чуть менее чем на 142%.

Мне трудно понять по этому коду. Вокруг всё круглое.

Сообщение от nullxdth

Кто мешает в таблицу по значению записывать меньшую по размеру строку и, далее, отобразить набор слов на эту таблицу 1 в 1?

Так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import std.stdio, std.string;
 
string[string] words;
 
void main() {
    
    short n, m;
    
    scanf("%hd%hd", &n, &m);
 
    foreach (i; 0 .. m) {
        auto word1 = readln(' ').strip;
        auto word2 = readln.strip;
        words[word1] = (word2.length < word1.length) ? word2 : word1;
    }
    
    foreach (idx, lecture; readln.split) {
        write(words[lecture]);
        write((idx == n - 1) ? '\n' : ' ');
    }
}

@nullxdth · 06.03.2015, 23:20

Сообщение от Dennis Ritchie

Так?

Ну да.
Только не понятно, зачем вот это говно нужно:

Сообщение от Dennis Ritchie

write((idx == n - 1) ? '\n' : ' ');

Сделай перевод строки после цикла и всё.
И почему у тебя таблица объявлена глобально, а n и m в области main? Это так в заборостроительном учат?

Добавлено через 52 секунды

Сообщение от Dennis Ritchie

Мне трудно понять по этому коду. Вокруг всё круглое.

Там тоже самое написано, точь в точь. Только синтаксис другой и всё.

Добавлено через 1 минуту

Сообщение от castorsky

146 же

Блин, точно.

@Dennis Ritchie · 06.03.2015, 23:28 **[ТС]**

Сообщение от nullxdth

Ну да.

Отлично. А почему этот более продвинутый алгоритм работает на максимальных тестах за 31 мс? А ты уверен, что длина строки будет вычисляться каждый раз? А ты не забыл про оптимизатор? А ты не забыл, что благодаря оптимизатору более тупой алгоритм может работать быстрее? А ты не забыл, что в твоём алгоритме нужно использовать дополнительную переменную word2? Оценка сложности отдыхает (поздравляю с успешным окончанием заборостроительного!).

Сообщение от nullxdth

Только не понятно, зачем вот это говно нужно:

Чтобы после последнего слова пробела не было.

Сообщение от nullxdth

И почему у тебя таблица объявлена глобально, а n и m в области main?

Привычка из C++ - делать массивы глобальными. И, по-моему, красиво смотрится.

Сообщение от nullxdth

Там тоже самое написано, точь в точь. Только синтаксис другой и всё.

Понятно.

@nullxdth · 06.03.2015, 23:52

Сообщение от Dennis Ritchie

А почему этот более продвинутый алгоритм работает на максимальных тестах за 31 мс?

Что ещё за максимальные тесты? Давай входные данные, померим.

Сообщение от Dennis Ritchie

А ты уверен, что длина строки будет вычисляться каждый раз?

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

Добавлено через 1 минуту

Сообщение от Dennis Ritchie

А ты не забыл про оптимизатор?

Ну-ка, расскажи мне, школьник, что там можно автоматически соптимизировать? Особенно на считанных из потока данных, лол?

Добавлено через 2 минуты

Сообщение от Dennis Ritchie

Привычка из C++ - делать массивы глобальными.

Это не привычка из С++, это школьный идиотизм.

Добавлено через 6 минут

Сообщение от Dennis Ritchie

А ты не забыл, что в твоём алгоритме нужно использовать дополнительную переменную word2?

Ха. И что, лол?

Ты думаешь это как-то влияет на производительность? Вообще никак, дочь. Если, конечно, в D lexical bindings не в rt создаются и при присваивании не происходит копирование.

Добавлено через 1 минуту

Сообщение от Dennis Ritchie

А ты не забыл, что благодаря оптимизатору более тупой алгоритм может работать быстрее?

Это сложный и очень спорный вопрос. С твоими навыками и знаниями, лучше даже не обсуждать это. В данной задаче, первое твоё решение не будет работать быстрее второго. Инфа 146% при отсутствии копирования при =.

Добавлено через 4 минуты

Сообщение от nullxdth

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

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

@Dennis Ritchie · 07.03.2015, 00:10 **[ТС]**

Сообщение от nullxdth

лексикографическое сравнение, то разница была бы очень ощутима.

Для лексикографического сравнения длина строки не важна. В D это делается так:

C++
1
word1 < word2

Сообщение от nullxdth

Что ещё за максимальные тесты? Давай входные данные, померим.

Нельзя скопировать. Вот сам посмотри:
Первое решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
﻿import std.stdio, std.string;
 
string[string] words;
 
void main() {
 
    short n, m;
 
    scanf("%hd%hd", &n, &m);
 
    foreach (i; 0 .. m) {
        auto tmp = readln(' ').strip;
        words[tmp] = readln.strip;
    }
 
    foreach (idx, lecture; readln.split) {
        write((lecture.length <= words[lecture].length) ? lecture : words[lecture]);
        write((idx == n - 1) ? '\n' : ' ');
    }
}

Второе решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
﻿import std.stdio, std.string;
 
string[string] words;
 
void main() {
    
    short n, m;
    
    scanf("%hd%hd", &n, &m);
 
    foreach (i; 0 .. m) {
        auto word1 = readln(' ').strip;
        auto word2 = readln.strip;
        words[word1] = (word2.length < word1.length) ? word2 : word1;
    }
    
    foreach (idx, lecture; readln.split) {
        write(words[lecture]);
        write((idx == n - 1) ? '\n' : ' ');
    }
}

Сообщение от nullxdth

но всё же выглядит твоё первое решение совершенно не пристойно.

Сначала я сам хотел решать, как ты предложил, но потом почему-то передумал и решил по-другому.

Сообщение от nullxdth

Ну-ка, расскажи мне, школьник, что там можно автоматически соптимизировать? Особенно на считанных из потока данных, лол?

Смешной ты студент:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
int main()
{
    int n;
    int x = 0;
  
    std::cin >> n;
  
    for( int i = 0; i < n + 1; ++i )
    {
        x += i;
    }
  
    return x;
}

Думаешь, что на данные из потока нельзя выделить дополнительную память? Например, для хранения длин строк в дополнительных переменных (если в последствии они будут использованы)? Думаешь, что оптимизатор тупой и на это не способен?

Сообщение от nullxdth

Это не привычка из С++, это школьный идиотизм.

Да. Мне школьный препод по информатике сказал, чтобы я лучше изучил D, а потом возвращался обратно в школу.

Сообщение от nullxdth

Ты думаешь это как-то влияет на производительность?

Немного должно.

@nullxdth · 07.03.2015, 00:41

Сообщение от Dennis Ritchie

Первое решение
Второе решение

Сдаётся мне это твой CodeForces по-мудацки считает. Особенно с учётом 1-ого теста, на котором 2-ой вариант умудрился посчитаться за 15мс, лол. Прогони ещё раз. А лучше давай отчёт профилировщика D-шного на тестах где 31мс по 1-му и 2-му решению, если ты его конечно осилил.

Добавлено через 2 минуты

Сообщение от Dennis Ritchie

Например, для хранения длин строк в дополнительных переменных

Это не оптимизация. Я про это уже написал, что размер берётся за O(1).

Добавлено через 54 секунды

Сообщение от Dennis Ritchie

Думаешь, что на данные из потока нельзя выделить дополнительную память?

А причём тут это? Мы же про вычисление размера строки, не?

Добавлено через 40 секунд

Сообщение от Dennis Ritchie

Думаешь, что оптимизатор тупой и на это не способен?

Оптимизатор тут ни при чём, дочь.

Добавлено через 2 минуты

Сообщение от Dennis Ritchie

Сначала я сам хотел решать, как ты предложил, но потом почему-то передумал и решил по-другому.

Манёвры? Просто признайся, мань, что не можешь даже в задачи уровня "Hello, world!". Пишешь какую-то ерунду. Ты, надеюсь, понимаешь, почему 2-ой вариант предпочтительней 1-ого?

Добавлено через 2 минуты

Сообщение от Dennis Ritchie

Для лексикографического сравнения длина строки не важна.

Сложность зависит от длины ещё как. В лучшем случае она O(n). Если это unicode строки и сравнивать по-честному, то это вообще ахтунг.

Добавлено через 12 минут

Сообщение от Dennis Ritchie

Немного должно.

И каким образом? (мы говорим про rt, если что)

@Dennis Ritchie · 07.03.2015, 00:46 **[ТС]**

Сообщение от nullxdth

Мы же про вычисление размера строки, не?

Выделить дополнительную память под длину строк.

Сообщение от nullxdth

В лучшем случае она O(n).

Ну так-то, да.

Сообщение от nullxdth

Прогони ещё раз.

Прогнал. Теперь тоже 15 мс выдаёт, но на первом тесте всё равно 15 мс.

Сообщение от nullxdth

А лучше давай отчёт профилировщика D-шного на тестах

Никогда не пользовался профилировщиком. Мог бы сейчас попробовать, но у меня в данный момент не работает Visual D, в котором есть профилировщик:
Profiling

Не по теме:

Сообщение от nullxdth

Ты, надеюсь, понимаешь, почему 2-ой вариант предпочтительней 1-ого?

Да, в отличие от студентов лесопильного мясокомбината. :D

Сообщение от nullxdth

И каким образом? (мы говорим про rt, если что)

Больше операций присваивания, больше памяти.

@castorsky · 07.03.2015, 00:58

Сообщение от Dennis Ritchie

Больше операций присваивания, больше памяти.

Поэтому присваивания не нужны

только pure functions which return values and functions. No access, no bind more than once, never algol68! xD

@Dennis Ritchie · 07.03.2015, 01:01 **[ТС]**

Сообщение от castorsky

только pure functions which return values and functions.

Но ведь на вызов функции тоже тратится немало ресурсов.

@castorsky · 07.03.2015, 01:01

Сообщение от Dennis Ritchie

Но ведь на вызов функции тоже тратится немало ресурсов

если это учитывать во время проектирования языка, то не так уж и немало, всего ничего.

@Dennis Ritchie · 07.03.2015, 03:05 **[ТС]**

Сообщение от castorsky

Поэтому присваивания не нужны

Ну это, как Дейкстра: "Давайте, будем создавать правильный код. Нельзя использовать goto!"

Сейчас опять у кого-нибудь заболит от этого кода голова (и он начнёт от завести фыркать, смеяться и кукарекать о том, насколько D плох

):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import std.stdio : writeln;
import std.range : sequence, recurrence;
import std.algorithm : take;
 
void main() {
 
    writeln("/**********************************/\n");
 
    auto odds = sequence!("a[0] + n * a[1]")(1, 2);
 
    writeln("odds = ", odds.front); // prints 1
 
    odds.popFront;
 
    writeln("odds = ", odds.front); // prints 3
 
    odds.popFront;
 
    writeln("odds = ", odds.front); // prints 5
 
    writeln("odds = ", odds[99899]);    // prints 199803
 
    writeln("\n/**********************************/\n");
 
    // a[0] = 1, a[1] = 1, and compute a[n+1] = a[n-1] + a[n]
    auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
    // print the first 10 Fibonacci numbers
    writeln("fib_10");
    foreach (e; take(fib, 10)) { writeln(e); }
    // print the first 10 factorials
    writeln("\nfact_10");
    foreach (e; take(recurrence!("a[n-1] * n")(1), 10)) { writeln(e); }
 
    writeln("\n/**********************************/");
}

@Voivoid · 07.03.2015, 12:53

Сообщение от Dennis Ritchie

words[word1] = (word2.length < word1.length) ? word2 : word1;

Нафига хранить все слова-то? Храни только те слова, которые меньше по размеру. Ибо лишние добавление узла к дереву - лишняя аллокация. Потом, во время подстановки смотри, если слово есть в ассоциативном массиве, то печатай его, если нет, печатай исходное

@nullxdth · 07.03.2015, 12:59

Сообщение от Voivoid

Нафига хранить все слова-то? Храни только те слова, которые меньше по размеру. Ибо лишние добавление узла к дереву - лишняя аллокация. Потом, во время подстановки смотри, если слово есть в ассоциативном массиве, то печатай его, если нет, печатай исходное

Точняк. Ё-моё.

@Dennis Ritchie · 07.03.2015, 13:07 **[ТС]**

Сообщение от Voivoid

Нафига хранить все слова-то?

Ну, да. Сейчас освобожусь, тогда настрочу новое решение. Скорость глянем.

@Voivoid · 07.03.2015, 13:10

Сообщение от Dennis Ritchie

Ну, да. Сейчас освобожусь, тогда настрочу новое решение. Скорость глянем.

Да в общем-то смысла нет смотреть. Будет или 15мс или 30мс. codeforces фигово считает время решений на коротких промежутках

@Dennis Ritchie · 07.03.2015, 13:50 **[ТС]**

Сообщение от Voivoid

Да в общем-то смысла нет смотреть. Будет или 15мс или 30мс. codeforces фигово считает время решений на коротких промежутках

Замерим чем-нибудь более продвинутым.

Добавлено через 39 минут
Да, Codeforces.ru опять показывает 31 мс. Наверное, сервер сейчас нагружен (многие решают, ведь день в разгаре). Надо замерять на профайлере.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import std.string : strip, split;
import std.stdio : scanf, readln, write;
 
string[string] words;
 
void main() {
    
    short n, m;
    
    scanf("%hd%hd", &n, &m);
    
    foreach (i; 0 .. m) {
        auto word1 = readln(' ').strip;
        auto word2 = readln.strip;
        if (word2.length < word1.length)
            words[word1] = word2;
    }
 
    foreach (idx, lecture; readln.split) {
        write(lecture in words ? words[lecture] : lecture);
        write((idx == n - 1) ? '\n' : ' ');
    }
}

Новые блоги и статьи Все статьи Все блоги /
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .