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' : ' ');
    }
}

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .	Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь