веб, ASP, начало

[OmegaBerkut]

Пепел Феникса
Как я понял, у этого вашего LinkedList нет собственной индексации, отсюда и костыли вроде "LinkListExtension". В моём классе эта функция включается по умолчанию. В MSDN нашёл нечто вроде ElementAt, но в объекте класса LinkedList этот метод не определён. И, это я ещё не лез в исходники дотнета, которые я скачал недавно.
К тому же ваша конструкция исключает возможность НЕ сохранять последовательность случайных индексов для доступа, о чём я уже упоминал.

Мой улучшенный метод (который я назвал карусельным) позволяет вытаскивать элементы по индексу чуть более чем в три раза быстрее (порядка 3,25), чем стандартный метод. Скорость создания колеблется в пределах +/-5% для обоих коллекций. Вы говорили, что двусвязный закольцованный список мне не поможет ...
Далее будут листинги.
Код переработанного моего класса

using System;

namespace Listing
{
	class StringListData
	{ // класс-хранилище элементов
		public StringListData(string newitem)
		{
			item=newitem;
			// первичная инициализация
			// дальнейшие параметры будут задаваться из-вне создания элемента
			prev=next=this; // закольцованный двусвязный список
			pos=0;
		}
		public StringListData
			prev, // ссылка на предыдущий элемент
			next; // ссылка на следующий элемент
		public int pos;
		public string item;
		// а ещё, тут можно хранить всё что хочешь, в любом количестве (ограничения только по RAM)
	}

	class StringList
	{ // класс-обработчик элементов хранилища
		public StringList() {}
		
		public StringListData
			first, // ссылка на первый элемент
			current; // ссылка на текущий элемент; часть карусели
		
		public void AddToLast(string newitem)
		{
			StringListData creating=new StringListData(newitem);
			if (first==null)
			// первичная инициализация списка
				first=current=creating;
			else
			{ // перестроение хвоста структуры
				current=this.first.prev; // так как добавление в конец - берём конец из начала
				creating.prev=this.current; // во вновь созданный элемент сохраняем предыдущий (текущий обрабатываемый)
				creating.next=this.first; // во вновь созданный элемент сохраняем следующий (закольцовка)
				creating.pos=this.current.pos+1; // следующий индекс
				this.current.next=creating; // добавление элемента в список
				this.first.prev=creating; // обратная закольцовка (так как список двусвязный)
			}
		}
		// разномастные методы добавления

		// последующие две функции обеспечивают основу карусели
		/* с таким подходом максимально возможное количество переходов по списку всегда в два раза меньше количества элементов
		списка; делить максимальное количество переходов по списку можно вплоть до создания полносвязной структуры, что по памяти
		равносильно созданию обычного массива, а по логике работы будет ахинея */
		private void SwitchToPrev(int count)
		{
			while (count>0)
			{
				current=current.prev;
				count--;
			}
		}
		private void SwitchToNext(int count)
		{
			while (count>0)
			{
				current=current.next;
				count--;
			}
		}
		public void SwitchToIndex(int index)
		{ // здесь выполняется расчёт минимального количества переходов в задаваемом направлении
			int
				count=first.prev.pos+1, // если в списке нет элементов - NRE
				position=current.pos,
				prevsteps=0,nextsteps=0;
			// если index>count - произойдёт зацикливание по списку; поднимать отдельное условие для этого не целесообразно
			if (index<position)
			{
				prevsteps=position-index;
				nextsteps=count-position+index;
			} else
			if (index>position)
			{
				prevsteps=count+position-index;
				nextsteps=0-position+index;
			} else {}
			if (prevsteps>nextsteps)
				SwitchToNext(nextsteps);
			else
			if (prevsteps<nextsteps)
				SwitchToPrev(prevsteps);
			else {}
		}

		public string this[int index]
		{ // собсна, индексатор; правда не массива, а класса, но не об этом
			get
			{
				SwitchToIndex(index);
				return current.item;
			}
			set
			{
				SwitchToIndex(index);
				current.item=value;
			}
		}

		// методы удаления элементов
		// согласен с тем, что при удалении элемента нужно выполнять ручную переиндексацию;
		// чем меньше индекс удаляемого элемента - тем больше элементов нужно переиндексировать

		~StringList()
		{ // это деструктор
			// здесь можно выполнять полную зачистку, без переиндексации
		}
	}
}

Код тестов

using System;
using System.Diagnostics;
using System.Collections.Generic;

namespace Listing
{
	class Program
	{
		private const int allseed=5; // из разных рандомов с одинаковым зерном будет получена одинаковая последовательность чисел
		private const int
			limit=5000, // размер списков
			requests=100000; // количество случайных обращений
		private static Stopwatch timer;

		static void TestLinkedList(ref long timecreate,ref long timerequest)
		{
			LinkedList<string> test=new LinkedList<string>();
			Random rnd=new Random(allseed);
			int i,num;
			string temp;
			timer.Restart();
			for (i=0;i<limit;i++)
				test.AddLast(i.ToString());
			timer.Stop();
			Console.WriteLine("LinkedList - creating time = "+timer.Elapsed.Ticks.ToString());
			timecreate=timer.Elapsed.Ticks;
			timer.Restart();
			LinkedListNode<string> node;
			for (i=0;i<requests;i++)
			{
				num=rnd.Next(limit);
				node=test.First; // мой метод этого лишён
				while (num>0)
				{
					node=node.Next;
					num--;
				}
				temp=node.Value;
			}
			timer.Stop();
			Console.WriteLine("LinkedList - request time = "+timer.Elapsed.Ticks.ToString());
			timerequest=timer.Elapsed.Ticks;
		}
		private static void TestStringList(ref long timecreate,ref long timerequest)
		{
			StringList test=new StringList();
			Random rnd=new Random(allseed);
			int i,num;
			string temp;
			timer.Restart();
			for (i=0;i<limit;i++)
				test.AddToLast(i.ToString());
			timer.Stop();
			Console.WriteLine("StringList - creating time = "+timer.Elapsed.Ticks.ToString());
			timecreate=timer.Elapsed.Ticks;
			test.current=test.first; // переход в начало списка, для чистоты эксперимента; что в прочем не обязательно
			timer.Restart();
			for (i=0;i<requests;i++)
			{
				num=rnd.Next(limit);
				temp=test[num];
			}
			timer.Stop();
			Console.WriteLine("StringList - request time = "+timer.Elapsed.Ticks.ToString());
			timerequest=timer.Elapsed.Ticks;
		}

		private static void Main(string[] args)
		{
			timer=new Stopwatch();
			long[] results=new long[4];
			byte i;
			repeat:;
			for (i=0;i<4;i++)
				results[i]=0;
			TestLinkedList(ref results[0], ref results[1]);
			Console.WriteLine();
			TestStringList(ref results[2], ref results[3]);
			Console.WriteLine(
				"\r\nCreate coefficient: "+(double)results[0]/results[2]+
				"\r\nRequest coefficient: "+(double)results[1]/results[3]);
			Console.ReadLine();
			Console.WriteLine();
			goto repeat;
		}
	}

}

Скрин результатов (вложением)

[OmegaBerkut]

Если коэффициент больше единицы - то это означает, что мой класс в этой части лучше стандартного.

К тому же, я так понимаю, что внутри List<T> спрятан обычный массив ссылок на объекты *. Потому что иначе я никак не объясню скорость ответа, примерно равную скорости вызова функции. И для убеждения в том, что и там есть что ускорить - я как нибудь залезу в исходник, посмотрю, как оно там устроено.
Что касается спора о том, как тестировать - я не буду возражать против того, что точетные замеры будут давать большие погрешности, во всяком случае не собираюсь проверять. И так сойдёт.
Не сохранять перечень псевдослучайных индексов можно, при чём для любого режима тестирования. Ключевой момент - псевдо: если конструктору рандома скармливать какое нибудь число - то в любой точке пространства/времени вы получите одинаковый набор чисел, ибо так он (рандом) устроен.

Теперь о звёздочке (*): по большому счёту, в объектах можно хранить произвольный набор данных, а в массиве хранить ссылки на эти объекты. Тогда линейно в памяти мы будем хранить только те самые ссылки (размер которых толи 4, то ли 8 байт), а сами объекты будут расположены где придётся.

[OmegaBerkut]

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

[Пепел Феникса]

К тому же ваша конструкция исключает возможность НЕ сохранять последовательность случайных индексов для доступа, о чём я уже упоминал.

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

К тому же, я так понимаю, что внутри List<T> спрятан обычный массив ссылок на объекты *. Потому что иначе я никак не объясню скорость ответа, примерно равную скорости вызова функции. И для убеждения в том, что и там есть что ускорить - я как нибудь залезу в исходник, посмотрю, как оно там устроено.

List<> это и есть массив
раз 5 это говорил.
но вы вообще-то тестировали LinkedList.

Теперь о звёздочке (*): по большому счёту, в объектах можно хранить произвольный набор данных, а в массиве хранить ссылки на эти объекты. Тогда линейно в памяти мы будем хранить только те самые ссылки (размер которых толи 4, то ли 8 байт), а сами объекты будут расположены где придётся.

для справки, любой класс в C# всегда хранится по ссылке.

// это деструктор

в C# нет деструкторов, это финализатор.
а это совсем иное.

Как я понял, у этого вашего LinkedList нет собственной индексации, отсюда и костыли вроде "LinkListExtension".

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

В MSDN нашёл нечто вроде ElementAt, но в объекте класса LinkedList этот метод не определён

.ElementAt это Linq, что тоже метод расширения.
снова пробел.

и да, я не думаю что это сильно удивительно что связанный список не имеет доступа по индексу, он не создан для этого



результаты честного теста.(вы решили проигнорировать мои разъяснения на этот счет)

Сообщение от 5000 Элементов: 100 итераций

TestOwn: 00:00:08.3192792 : 83,19 : 194541
TestOwn2: 00:00:04.0447605 : 40,44 : 94584
TestSL: 00:00:04.4467083 : 44,46 : 103983

Сообщение от 5000 Элементов: 1000 итераций

TestOwn: 00:01:24.2782511 : 84,278 : 197080
TestOwn2: 00:00:40.9461868 : 40,946 : 95750
TestSL: 00:00:43.9186437 : 43,918 : 102701

Сообщение от 50000 Элементов: 5 итераций

TestOwn: 00:00:53.3799905 : 10675,8 : 24965234
TestOwn2: 00:00:26.3961136 : 5279,2 : 12345172
TestSL: 00:00:33.1793298 : 6635,8 : 15517607

как можно заменить пропорции всегда примерно одинаковы.
хотя есть ситуации где ваш код мог бы выиграть, но в чисто рандомном доступе он проигрывает.
TestOwn2 отличается от TestOwn тем что выполняет двунаправленный поиск.(либо с конца, либо с начала, а не только с начала как TestOwn)

как вы можете заметить я вас еще и специально ввел в этот тест.(кстати остальные аргументы против вашего подхода вы тоже проигнорировали)
я ведь не спроста говорил про string.Join что не доступен вашему классу.(и многое иное, например распараллеливание обработки готовое, вам тоже не доступно, а значит снова будете писать свое...)
для задачи где нужно оптимальное применение памяти и максимальная скорость доступа, я бы написал некий Partioned storage(сочетание списка и массива)

так что думайте, стоит ли продолжать тратить свое время.*

за сим, удачи вам
советую вернутся к топику темы все же.


* - если сравнить время потраченное, результат будет еще хуже.
я потратил пару минут на расширение класса, ваш же класс был написан с нуля.
+ мне не придется переделывать класс для LinkedList<int>, вам, придется.
я надеюсь вы все же перестанете заниматься лишней работой(ну или жизнь заставит, когда на работу пойдете, как тот из-за кого уволили пару человек, я могу так говорить)

[OmegaBerkut]

Пепел Феникса
Я уже не один раз говорил, что мои обращения всегда одинаковы, с одним лишь отличием от ваших - я не создаю массив, а испоьзую способность ГПСЧ выдавать одинаковые последовательности.
Моя карусель так же выполняет двунаправленный переход (стоит заметить, что это не поиск), только не с начала / с конца, а от последней позиции, что максимально приближается к условиям случайности.
Я трачу на это время лишь потому что мне это интересно.

Что касается того, что ссылочный список не создан для индексации - я придумал, как избавиться от проблем при удалении элемнтов: опять же, не таскать индекс за каждым элементом, а пересчитывать его по мере перемещения по списку.
В моём коде, кстати, не будет перемещения по списку в том случае, если в обоих направлениях будет одинаковое количество переходов - для случаев, когда количество элементов нечётное. Тут не хватает одного символа равно.

На счёт тестов: скажите на основе конкретного кода - что я не учитываю ?

[Пепел Феникса]

Что касается того, что ссылочный список не создан для индексации - я придумал, как избавиться от проблем при удалении элемнтов: опять же, не таскать индекс за каждым элементом, а пересчитывать его по мере перемещения по списку.

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

Я уже не один раз говорил, что мои обращения всегда одинаковы, с одним лишь отличием от ваших - я не создаю массив, а испоьзую способность ГПСЧ выдавать одинаковые последовательности.

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

На счёт тестов: скажите на основе конкретного кода - что я не учитываю ?

1)Debug режим(а походу еще и отладка)
2)У вас нет сглаживания погрешностей.(тики кстати говоря, это не тики инструкций, а тики системного таймера, что совсем разное)
3)нет учета сборщика мусора и потребления памяти.

В моём коде, кстати, не будет перемещения по списку в том случае, если в обоих направлениях будет одинаковое количество переходов - для случаев, когда количество элементов нечётное. Тут не хватает одного символа равно.

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

if(a<b) { /*a<b*/ } else { /*a>=b*/ }

?

[OmegaBerkut]

Пепел Феникса
Два сравнения делаю для того, что бы не считать лишний раз количество переходов, собсна поэтому и прозевал равное их кол-во для нечётного кол-ва элементов.

Скриншот не из отладки, и вне дебага (что кстати одно и тоже на разных языках) ... Просто запуск экзешника из папки проекта.
Что за сглаживание погрешностей ? Я перед заходом в цикл стартую таймер, а после выхода отключаю этот же таймер; потом только снимаю результаты. Насколько мне известно - тики из stopwatch - это как раз таки параметры тактового генератора процессора. А точность системного таймера находится на уровне 20 миллисекунд (поэтому таймер из форм лучше не использовать для точных вычислений)

Upd
Про память и сборщик мусора не понял ... Я нигде не освобождаю память, что бы работал сборщик, а выделение памяти равнозначно для обоих коллекций.

[Пепел Феникса]

Насколько мне известно - тики из stopwatch - это как раз таки параметры тактового генератора процессора.

это тики таймера который применялся для измерений.
какой таймер применяется показывает свойство класса Stopwatch.
(уж явно не такты процессора)

Два сравнения делаю для того, что бы не считать лишний раз количество переходов, собсна поэтому и прозевал равное их кол-во для нечётного кол-ва элементов.

там нет смысла в двух сравнениях, у вас два выхода, а не три.

Скриншот не из отладки, и вне дебага (что кстати одно и тоже на разных языках) ... Просто запуск экзешника из папки проекта.

если что окно пишет путь к exeшнику, и там я вижу сборку Debug.

Debug - это конфигурация построения.
отладка - это собственно отладка.
тут нет разных языков.

Я нигде не освобождаю память

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

Я трачу на это время лишь потому что мне это интересно.

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

[OmegaBerkut]

Пепел Феникса
И чем же отличается конфигурация сборки дебаг от релиза ? При условии, что я запускаю екзешник из папки, а не (Ctrl+)F5 в студии.
В пределах кода во время замера область видимости не изменяется. Таймер сделан глобальным лишь для удобства. Если говорить об области видимости внутри кода коллекций - то у каждого класса свои переменные, и свои внутренние данные - и сводить обработку этих данных к погрешности ни в коем случае нельзя. Ибо если в LinkedList есть локальная переменная temp (скажем в функции AddLast), то на её создание и удаление так же будет затрачено время, которое так же необходимо учитывать. Тоже самое справедливо и для моего класса.

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

[Alex11223]

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

И чем же отличается конфигурация сборки дебаг от релиза ?

Отсутствием оптимизаций, наличием ассертов и прочих отладочных вещей.