Информация об изменениях

Сообщение Re[4]: Задолбал Dick Seek со своей "невнимательностью" от 26.11.2025 7:57

Изменено 26.11.2025 7:57 Философ

Старый текст
Новый текст
Разница

Re[4]: Задолбал Dick Seek со своей "невнимательностью"

Здравствуйте, VladD2, Вы писали:

У меня времени немного, поэтому отвечаю пока на это небольшое подмножество реплик.

Ф>>Потому что HashSet более тяжеловесный — по крайней мере он опирается на хэш, который тут нафиг не упал, и добавление O(1) он не гарантирует. Потому что заранее известно, что ключи уникальны и как-либо гарантировать их уникальность не нужно.

VD>Чушь полная. HashSet и Dictionary очень даже лехковесный. Данные там хранятся в одном списке, а доступ идет за ~константное время. Для современных процессоров LinkedList вообще не лучший выбор, так как ухудшает локальность памяти (узлы шире и могут располагаться в разных участках памяти).

Влад, а подумать!?
Специально для тебя эксперимент провёл. Сам бы этого не делал — и так знал.

код

using System;
using System.Collections.Generic;

namespace ADT_SpeedTest
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new List<string>();
            var llist = new LinkedList<string>();
            var hashSet = new HashSet<string>();

            const int maxI = 256;
            const int maxJ = 20;
            const int total = maxI * maxJ;

            var array = new string[total];
            for (int j = 0; j < total; j++){
                array[j] = j.ToString("D7");
            }

            for (int i = 0; i < maxI; i++){
                int max = 20 * (1 + i);
                Console.Write(max);
                Console.Write("  ");

                var sw = System.Diagnostics.Stopwatch.StartNew();
                for (int j = 0; j < max; j++){
                    list.Add(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    llist.AddLast(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    hashSet.Add(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");
                //===================================================

                for (int j = 0; j < max; j++){
                    list.Remove(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    llist.RemoveFirst();
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    hashSet.Remove(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);

                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}

[cut = попробуй угадать, где кто (.net 4.8, AnyCPU, Release, w/o debug)]

[/cut]

Ф>>Это индекс очередного символа в source — само собой там символы из source итерируются.

VD>Вот именно! И там явно перебор еще один. А два вложенных цикла — это O(n²)

Это если ты итерируешься по одному и тому же. Пример: если сравнивать все символы со всеми символами текста, то будет квадрат, если сравнивать символы ключей с символами текста, то будет произведение кол-ва символов ключей на кол-во символов текста. Это очень разные множества.
Вот, прикинь, у тебя может быть 20 — 30 ключей (мой случай) и ещё много букав в тексте.
допустим ключей 20, по 4 символа
текст — 100М

Тогда:
O(n²) — 100М*100М
O(n*m) — 100М*20*4

Re[4]: Задолбал Dick Seek со своей "невнимательностью"

код

using System;
using System.Collections.Generic;

namespace ADT_SpeedTest
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new List<string>();
            var llist = new LinkedList<string>();
            var hashSet = new HashSet<string>();

            const int maxI = 256;
            const int maxJ = 20;
            const int total = maxI * maxJ;

            var array = new string[total];
            for (int j = 0; j < total; j++){
                array[j] = j.ToString("D7");
            }

            for (int i = 0; i < maxI; i++){
                int max = 20 * (1 + i);
                Console.Write(max);
                Console.Write("  ");

                var sw = System.Diagnostics.Stopwatch.StartNew();
                for (int j = 0; j < max; j++){
                    list.Add(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    llist.AddLast(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    hashSet.Add(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");
                //===================================================

                for (int j = 0; j < max; j++){
                    list.Remove(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    llist.RemoveFirst();
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);
                Console.Write("  ");

                sw.Restart();
                for (int j = 0; j < max; j++){
                    hashSet.Remove(array[j]);
                }
                sw.Stop();
                Console.Write(sw.ElapsedTicks);

                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}

	попробуй угадать, где кто (.net 4.8, AnyCPU, Release, w/o debug)

Ф>>Это индекс очередного символа в source — само собой там символы из source итерируются.

VD>Вот именно! И там явно перебор еще один. А два вложенных цикла — это O(n²)

Это если ты итерируешься по одному и тому же. Пример: если сравнивать все символы со всеми символами текста, то будет квадрат, если сравнивать символы ключей с символами текста, то будет произведение кол-ва символов ключей на кол-во символов текста. Это очень разные множества.
Вот, прикинь, у тебя может быть 20 — 30 ключей (мой случай) и ещё много букав в тексте.
допустим ключей 20, по 4 символа
текст — 100М

Тогда:
O(n²) — 100М*100М
O(n*m) — 100М*20*4