Здравствуйте, Passerby, Вы писали:
P>А есть ли возможность делать сортировку быстрее, как-нибудь убрав Linq?
добавлю, что вот этот способ сортировки для LIst<T> наиболее худший:
List< int[]>[] arlarsort = new List<int[]>[c1];
for (int i = 0; i < arlar.Length; i++)
{
arlarsort[i] = arlar[i].OrderByDescending(pair => pair[1]).ToList();
}
у LIst<T> есть спец. метод LIst<T>.Sort(IComparer<T>), который сортирует in-place, не выделяя память и не создавая новый объек.
0. Нет, неверно. Прикрутите benchmarknet.org — без него вы понятия не имеете, какую точность результатов вы получаете. P>Необходимо пополнять какую-нибудь коллекцию парами string, int и после заполнения сортировать по убыванию int. Попробовал разные варианты в прилагаемом коде. Только сомнения в том, верно ли написал тест: код содержит OrderByDescending(pair => pair.Value, не будет ли отложенного выполнения уже после вывода результата?
1. Нет, у вас же везде сразу после него идёт материализация результата (ToDictionary()/ToArray())
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Passerby, Вы писали:
P>Необходимо пополнять какую-нибудь коллекцию парами string, int и после заполнения сортировать по убыванию int. Попробовал разные варианты в прилагаемом коде. Только сомнения в том, верно ли написал тест: код содержит OrderByDescending(pair => pair.Value, не будет ли отложенного выполнения уже после вывода результата?
1) вот это по вашему вы сортируете (по убыванию int)?:
Здравствуйте, Passerby, Вы писали:
P>По спецификации словаря так, действительно, делать нельзя. Но пока реализация словаря выполнена в виде структуры структур, то можно.
Этот набор слов непонятен. Реализация словаря выполнена в виде hash map, и у неё порядок элементов не совпадает с порядком добавления.
P>Какой выход?
Кэшировать:
public class myReverserClass : IComparer
{
private IComparer _caseInsensitiveComparer = new new CaseInsensitiveComparer();
int IComparer.Compare(Object x, Object y) => _caseInsensitiveComparer.Compare(x,y);
}
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Passerby, Вы писали:
P>У меня из словаря после сортировки ничего не удаляется и ничего не добавляется.
вообще, я так понимаю, что программирование вам не очень знакомо? или очень?
потому что довольно странные ваши, э-э... действия.
то, что я писал выше про словарь, из этого по моему можно сделать такой вывод:
поскольку сам по себе словарь с понятием сортировки не совместим, а наблюдаемое явление — спецэффект, то
это означает, что в дальнейшем он (спецэффект) может неожиданным образом исчезнуть/измениться, по причине например внесения изменений в классы BCL.
(уж не знаю зачем: оптимизация, или у кого-то нога левая так захочет)
при этом у вас где-то там в логике вашей программы заложено, что у словаря якобы вот такое поведение (как бы сортировка).
после чего ваша программа неожиданным образом ведет себя непредсказуемо. (может она у вас на атомной станции работает — и тю-тю...)
Измерять скорость сортировки разных коллекций, содержащих разные данные, — плохая идея. Экземпляр Random надо инициализировать одним и тем же значением seed перед каждым тестом, чтобы данные в коллекциях были идентичными.
Ну и да, прикрутить к проекту nuget-пакет BenchmarkDotNet намного проще, чем писать обвязку для теста (обычно неправильно) самому.
Необходимо пополнять какую-нибудь коллекцию парами string, int и после заполнения сортировать по убыванию int. Попробовал разные варианты в прилагаемом коде. Только сомнения в том, верно ли написал тест: код содержит OrderByDescending(pair => pair.Value, не будет ли отложенного выполнения уже после вывода результата?
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace Сравнение_скорости_словаря_и_списка
{
class Program
{
public class myReverserClass : IComparer
{
int IComparer.Compare(Object x, Object y)
{
return ((new CaseInsensitiveComparer()).Compare(x,y ));
}
}
public class myReverserClass1 : IComparer
{
int IComparer.Compare(object x, object y)
{
StrInt x1 = (StrInt)x;StrInt y1 = (StrInt)y;
return ((new CaseInsensitiveComparer()).Compare(y1.ii,x1.ii ));
}
}
class StrInt
{
public string str;
public int ii;
public StrInt(string str, int ii)
{ this.str = str; this.ii = ii; }
}
static void Main(string[] args)
{
Random rnd = new Random();
int c1 = 10000, c2 = 50;
Stopwatch sw = new Stopwatch();
//1
sw.Start();
Dictionary<string, int>[] ardic = new Dictionary<string, int>[c1];
for (int i = 0; i < ardic.Length; i++)
{
var dic = new Dictionary<string, int>(c2);
ardic[i] = dic;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
dic.Add(j.ToString(), value);
}
}
sw.Stop(); TimeSpan tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
Dictionary<string, int>[] ardicsort = new Dictionary<string, int>[c1];
for (int i = 0; i < ardic.Length; i++)
{
ardicsort[i] = ardic[i].OrderByDescending(pair => pair.Value).ToDictionary(pair => pair.Key, pair => pair.Value);
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
//2
sw.Restart();
List<(string, int)>[] arl = new List<(string, int)>[c1];
for (int i = 0; i < arl.Length; i++)
{
var l = new List<(string, int)>(c2);
arl[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add((j.ToString(), value));
}
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
List<(string, int)>[] arlsort = new List<(string, int)>[c1];
for (int i = 0; i < arl.Length; i++)
{
arlsort[i] = arl[i].OrderByDescending(pair => pair.Item2).ToList();
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
//3 на всякий случай проверяю не string,int а int,int
sw.Restart();
List< int[]>[] arlar = new List< int[]>[c1];
for (int i = 0; i < arlar.Length; i++)
{
var l = new List< int[]>(c2);
arlar[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add(new[] { j, value});
}
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
List< int[]>[] arlarsort = new List<int[]>[c1];
for (int i = 0; i < arlar.Length; i++)
{
arlarsort[i] = arlar[i].OrderByDescending(pair => pair[1]).ToList();
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
//4
sw.Restart();
List<(string, int)>[] arl1 = new List<(string, int)>[c1];
for (int i = 0; i < arl1.Length; i++)
{
var l = new List<(string, int)>(c2);
arl1[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add((j.ToString(), value));
}
}
(string, int)[][] arart = new (string, int)[arl1.Length][];
for (int i = 0; i < arl1.Length; i++)
{ arart[i] = arl1[i].ToArray(); }
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
(string, int)[][] arartsort = new (string, int)[arart.Length][];
for (int i = 0; i < arart.Length; i++)
{
arartsort[i] = arl1[i].OrderByDescending(pair => pair.Item2).ToArray();
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
//5
sw.Restart();
List<StrInt>[] arlStrInt = new List<StrInt>[c1];
for (int i = 0; i < arlStrInt.Length; i++)
{
var l = new List<StrInt>(c2);
arlStrInt[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add(new StrInt(j.ToString(), value));
}
}
StrInt[][] ararStrInt = new StrInt[arlStrInt.Length][];
for (int i = 0; i < arlStrInt.Length; i++)
{ ararStrInt[i] = arlStrInt[i].ToArray(); }
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
IComparer myComparer1 = new myReverserClass1();
for (int i = 0; i < ararStrInt.Length; i++)
{
StrInt[] si = ararStrInt[i];
Array.Sort(si,myComparer1);
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
//6
sw.Restart();
List<string>[] arl21 = new List<string>[c1];
List<int>[] arl22 = new List<int>[c1];
for (int i = 0; i < arl21.Length; i++)
{
var l1 = new List<string>(c2); arl21[i] = l1;
var l2 = new List<int>(c2); arl22[i] = l2;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l1.Add(j.ToString()); l2.Add(value);
}
}
string[][] arars1 = new string[arl21.Length][];
int[][] arari2 = new int[arl22.Length][];
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
IComparer myComparer = new myReverserClass();
for (int i = 0; i < arars1.Length; i++)
{
string[] ars = arl21[i].ToArray();//arars1[i]int[] ari = arl22[i].ToArray();//arari2[i]
Array.Sort(ars,ari , myComparer);
arars1[i] = ars; arari2[i] = ari;
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
{ }
}
}
}
А есть ли возможность делать сортировку быстрее, как-нибудь убрав Linq?
Здравствуйте, Igorxz, Вы писали:
I>Здравствуйте, Passerby, Вы писали:
P>>Необходимо пополнять какую-нибудь коллекцию парами string, int и после заполнения сортировать по убыванию int. Попробовал разные варианты в прилагаемом коде. Только сомнения в том, верно ли написал тест: код содержит OrderByDescending(pair => pair.Value, не будет ли отложенного выполнения уже после вывода результата?
I>1) вот это по вашему вы сортируете (по убыванию int)?: I>
I>словарь (тот кокторый Dictionary< K, T >) по природе своей _не_ сортирован. I>все совпадения случайны.
По спецификации словаря так, действительно, делать нельзя. Но пока реализация словаря выполнена в виде структуры структур, то можно. Но это вообще не принципиально. Можно не делать .ToDictionary(pair => pair.Key, pair => pair.Value);, а создать OrderedDictionary и в цикле IEnumerable заполнить его значениями. Мне гораздо интереснее можно ли саму сортировку сделать быстрее, уйти как-нибудь от Linq.
I>2) чем бы там ни было CaseInsensitiveComparer, но вот этот код нехило нагрузит GC первым мусорным поколением: I>
Здравствуйте, Passerby, Вы писали:
P>А есть ли возможность делать сортировку быстрее, как-нибудь убрав Linq?
сделать быстрее чем что? чем заполнение List<(string, int)>'а с последующей сортировкой?
для каких данных? для каких объемов данных?
сразу скажу, по своему опыту, что например для 500_000 и более строк, совсем не сортированных, из готового в BCL
c заполнением List< string >'а с последующей сортировкой сравниться только SortedSet< string >, _но_ т.к. это по структуре Red-Black-Tree,
то памяти будет жрать больше, чем List< string >, и как следствие больше грузить GC.
из самодельного (опять же — для 500_000 и более строк) быстрее заполнения List< string >'а с последующей сортировкой
будет например самодельная реализация а-ля B-Plus-Tree.
(вообщем смысл — минимизировать копирования кусков памяти при вставке данных)
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Passerby, Вы писали:
P>>По спецификации словаря так, действительно, делать нельзя. Но пока реализация словаря выполнена в виде структуры структур, то можно. S>Этот набор слов непонятен. Реализация словаря выполнена в виде hash map, и у неё порядок элементов не совпадает с порядком добавления.
Там деление блоков по хэшу начинается после какого-то (кажется 1000-го) элемента. У меня меньше.
Random rnd = new Random();
int c1 = 10000, c2 = 50;
Dictionary<string, int> dict = new Dictionary<string, int>(c2);
for (int i = 0; i < c2; i++)
{
dict.Add(rnd.Next().ToString(), i);
}
{ }
Не нашел как добавить рисунок, который показывает сохранение порядка в этом коде.
P>>Какой выход? S>Кэшировать: S>
S> public class myReverserClass : IComparer
S> {
S> private IComparer _caseInsensitiveComparer = new new CaseInsensitiveComparer();
S> int IComparer.Compare(Object x, Object y) => _caseInsensitiveComparer.Compare(x,y);
S> }
S>
Здравствуйте, Passerby, Вы писали:
P>Здравствуйте, Sinclair, Вы писали:
S>>Здравствуйте, Passerby, Вы писали:
P>>>По спецификации словаря так, действительно, делать нельзя. Но пока реализация словаря выполнена в виде структуры структур, то можно. S>>Этот набор слов непонятен. Реализация словаря выполнена в виде hash map, и у неё порядок элементов не совпадает с порядком добавления. P>Там деление блоков по хэшу начинается после какого-то (кажется 1000-го) элемента. У меня меньше. P>
P>Random rnd = new Random();
P> int c1 = 10000, c2 = 50;
P> Dictionary<string, int> dict = new Dictionary<string, int>(c2);
P> for (int i = 0; i < c2; i++)
P> {
P> dict.Add(rnd.Next().ToString(), i);
P> }
P> { }
P>
P>Не нашел как добавить рисунок, который показывает сохранение порядка в этом коде.
это не важно. это просто спецэффект))) такой)))
хэш-таблица по своей сути не сортированна.
это ассоциативный массив, в которм адресация происходит с помощью операции свертики...
Здравствуйте, Igorxz, Вы писали:
I>Здравствуйте, Passerby, Вы писали:
P>>Здравствуйте, Sinclair, Вы писали:
S>>>Здравствуйте, Passerby, Вы писали:
P>>>>По спецификации словаря так, действительно, делать нельзя. Но пока реализация словаря выполнена в виде структуры структур, то можно. S>>>Этот набор слов непонятен. Реализация словаря выполнена в виде hash map, и у неё порядок элементов не совпадает с порядком добавления. P>>Там деление блоков по хэшу начинается после какого-то (кажется 1000-го) элемента. У меня меньше. P>>
P>>Random rnd = new Random();
P>> int c1 = 10000, c2 = 50;
P>> Dictionary<string, int> dict = new Dictionary<string, int>(c2);
P>> for (int i = 0; i < c2; i++)
P>> {
P>> dict.Add(rnd.Next().ToString(), i);
P>> }
P>> { }
P>>
P>>Не нашел как добавить рисунок, который показывает сохранение порядка в этом коде.
I>это не важно. это просто спецэффект))) такой))) I>хэш-таблица по своей сути не сортированна. I>это ассоциативный массив, в которм адресация происходит с помощью операции свертики...
Что значит спецэффект? Объясните, почему заполнение списка идет в порядке заполнения словаря?
Random rnd = new Random();
int c1 = 10000, c2 = 50;
Dictionary<string, int> dict = new Dictionary<string, int>(c2);
for (int i = 0; i < c2; i++)
{
dict.Add(rnd.Next().ToString(), i);
}
List<(string, int)> lsi = new List<(string, int)>(c2);
foreach (var v in dict)
{
lsi.Add((v.Key, v.Value));
}
{ }
Здравствуйте, Igorxz, Вы писали:
I>Здравствуйте, Passerby, Вы писали:
P>>А есть ли возможность делать сортировку быстрее, как-нибудь убрав Linq? I>добавлю, что вот этот способ сортировки для LIst<T> наиболее худший: I>
I>List< int[]>[] arlarsort = new List<int[]>[c1];
I>for (int i = 0; i < arlar.Length; i++)
I>{
I> arlarsort[i] = arlar[i].OrderByDescending(pair => pair[1]).ToList();
I>}
I>
I>у LIst<T> есть спец. метод LIst<T>.Sort(IComparer<T>), который сортирует in-place, не выделяя память и не создавая новый объек.
Пытаюсь так
public class myReverserClassTuple : IComparer
{
private IComparer _caseInsensitiveComparer = new CaseInsensitiveComparer();
int IComparer.Compare(Object x, Object y)
{ var x1 = (((string, int))x).ToTuple().Item2;object y1=(((string, int))y).ToTuple().Item2; return _caseInsensitiveComparer.Compare(x1, y1); }
}
чтобы далее
sw.Restart();
List<(string, int)>[] arl = new List<(string, int)>[c1];
for (int i = 0; i < arl.Length; i++)
{
var l = new List<(string, int)>(c2);
arl[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add((j.ToString(), value));
}
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
List<(string, int)>[] arlsort = new List<(string, int)>[c1];
IComparer myComparer11 = new myReverserClassTuple();
for (int i = 0; i < arl.Length; i++)
{
arlsort[i] = arl[i].Sort(myComparer11);
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
Но на строке arlsort[i] = arl[i].Sort(myComparer11); ошибка. Как правильно?
Здравствуйте, Passerby, Вы писали:
P>Что значит спецэффект?
спецэффект — это такой побочный эффект, который, даже если и есть, не предусмотрен/не запланирован идеей/концепцией.
но может устойчиво возникать при определенных обстоятельствах.
типа ветер дует, потому что деревья качаются)))
P>Объясните, почему заполнение списка идет в порядке заполнения словаря?
что значит заполнение списка идет в порядке заполнения словаря? непонятно.
если речь про то, что словарь из сортированного источника заполняется как бы то же сортировано, то это спецэффект))
вот пример кода, когда "как бы сортированный" словарь после удалений и пере-добавлений пересттает быть "как бы сортированным":
using System;
using System.Collections.Generic;
using System.Linq;
namespace __XZ__
{
/// <summary>
///
/// </summary>internal static class Program
{
[STAThread] private static void Main()
{
//ordered by ascvar array = Enumerable.Range( 'a', 'z' - 'a' + 1 ).Select( i => ((char) i).ToString() ).ToArray();
DictionaryFill_Test( array );
Console.ForegroundColor = ConsoleColor.DarkGray;
Console.WriteLine( "\r\n\r\n[.....finita.....]" );
Console.ReadLine();
}
private static void DictionaryFill_Test( IList< string > lst )
{
var dict = new Dictionary< string, string >();
dict.Fill( lst );
Console.WriteLine( "Dictionary fill #1:" );
dict.ToConsole();
var rnd = new Random( 42 );
for ( var j = 1; j <= 10; j++ )
{
var mod = rnd.Next( 1, 4 );
dict.Remove( lst.Where( (_, i) => (i % mod) == 0 ) );
dict.Fill( lst );
Console.WriteLine( $"Dictionary random-remove & fill #{j}:" );
dict.ToConsole();
}
}
private static void Fill( this Dictionary< string, string > dict, IEnumerable< string > appendKeys )
{
foreach ( var key in appendKeys )
{
if ( !dict.ContainsKey( key ) )
{
dict.Add( key, key );
}
}
}
private static void Remove< K, T >( this Dictionary< K, T > dict, IEnumerable< K > removedKeys )
{
foreach ( var key in removedKeys )
{
dict.Remove( key );
}
}
private static void ToConsole< K, T >( this Dictionary< K, T > dict )
{
Console.WriteLine( "--------------------------------------" );
foreach ( var p in dict )
{
Console.WriteLine( $"'{p.Key}', '{p.Value}'" );
}
Console.WriteLine( "--------------------------------------\r\n" );
}
}
}
Здравствуйте, Igorxz, Вы писали:
I>Здравствуйте, Passerby, Вы писали:
P>>Но на строке arlsort[i] = arl[i].Sort(myComparer11); ошибка. Как правильно? I>
I>public class myReverserClassTuple : IComparer< (string, int) >
I>
Сделал так:
public class myReverserClassTuple : IComparer<(string, int)>
{
public int Compare((string, int) t1,(string, int) t2)
{
if (t1.Item2 > t2.Item2)
return 1;
else if (t1.Item2 < t2.Item2)
return -1;
else
return 0;
}
}
и в программе:
sw.Restart();
List<(string, int)>[] arl = new List<(string, int)>[c1];
for (int i = 0; i < arl.Length; i++)
{
var l = new List<(string, int)>(c2);
arl[i] = l;
for (int j = 0; j < c2; j++)
{
int value = rnd.Next();
l.Add((j.ToString(), value));
}
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
sw.Restart();
var myComparer11 = new myReverserClassTuple();
for (int i = 0; i < arl.Length; i++)
{
List<(string, int)> l = arl[i];
l.Sort(myComparer11);
}
tsp = new TimeSpan(); tsp += sw.Elapsed;
Console.WriteLine(tsp);
}
а этот код тоже нехило нагрузит GC первым мусорным поколением или все норм?
Здравствуйте, Igorxz, Вы писали:
I>Здравствуйте, Passerby, Вы писали:
P>>Что значит спецэффект?
I>спецэффект — это такой побочный эффект, который, даже если и есть, не предусмотрен/не запланирован идеей/концепцией. I>но может устойчиво возникать при определенных обстоятельствах. I>типа ветер дует, потому что деревья качаются)))
P>>Объясните, почему заполнение списка идет в порядке заполнения словаря? I>что значит заполнение списка идет в порядке заполнения словаря? непонятно. I>если речь про то, что словарь из сортированного источника заполняется как бы то же сортировано, то это спецэффект))
I>вот пример кода, когда "как бы сортированный" словарь после удалений и пере-добавлений пересттает быть "как бы сортированным":
У меня из словаря после сортировки ничего не удаляется и ничего не добавляется.
Здравствуйте, Passerby, Вы писали:
P>Необходимо пополнять какую-нибудь коллекцию парами string, int и после заполнения сортировать по убыванию int. Попробовал разные варианты в прилагаемом коде. Только сомнения в том, верно ли написал тест: код содержит OrderByDescending(pair => pair.Value, не будет ли отложенного выполнения уже после вывода результата?
