Здравствуйте, 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");
}
Console.Write(" ");
for (int i = 0; i < maxI; i++){
int max = 20 * (1 + i);
Console.Write(max);
Console.Write(" ");
var sw = System.Diagnostics.Stopwatch.StartNew();//B
for (int j = 0; j < max; j++){
list.Add(array[j]);
}
sw.Stop();
Console.Write(sw.ElapsedTicks);
Console.Write(" ");
sw.Restart();//C
for (int j = 0; j < max; j++){
llist.AddLast(array[j]);
}
sw.Stop();
Console.Write(sw.ElapsedTicks);
Console.Write(" ");
sw.Restart();//D
for (int j = 0; j < max; j++){
hashSet.Add(array[j]);
}
sw.Stop();
Console.Write(sw.ElapsedTicks);
Console.Write(" ");
//===================================================
sw.Restart();//E
for (int j = 0; j < max; j++){
list.Remove(array[j]);
}
sw.Stop();
Console.Write(sw.ElapsedTicks);
Console.Write(" ");
sw.Restart();//F
for (int j = 0; j < max; j++){
llist.RemoveFirst();
}
sw.Stop();
Console.Write(sw.ElapsedTicks);
Console.Write(" ");
sw.Restart();//G
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
