ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Реализация List<t>
6 сообщений из 6, страница 1 из 1
Реализация List<t>
    #39221972
FatherSql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
FatherSql
Участник
гуглил, не получилось найти. Лист по идее это лист - то есть связный список. Тогда доступ по индексу занимает О(n). Но вроде как у List он занимает O(1). Получается что там устройство хитрое. Какое?
...
Рейтинг: 0 / 0
22.04.2016, 02:16
| Ответить | Цитировать | Написать  
Реализация List<t>
    #39221979
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сон Веры Павловны
Участник
FatherSqlЛист по идее это лист - то есть связный список. Тогда доступ по индексу занимает О(n). Но вроде как у List он занимает O(1). Получается что там устройство хитрое. Какое?
List<T> - это просто враппер на массивом, никакой связности там нет. Связный список - это LinkedList<T> (и в дотнете у него, кстати, нет своего собственного метода доступа по индексу).
FatherSqlгуглил, не получилось найти.
Лучше всего про это написано в исходниках .
...
Рейтинг: 0 / 0
22.04.2016, 03:02
| Ответить | Цитировать | Написать  
Реализация List<t>
    #39222018
FatherSql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
FatherSql
Участник
нету чтоли добавления в середину?
...
Рейтинг: 0 / 0
22.04.2016, 08:19
| Ответить | Цитировать | Написать  
Реализация List<t>
    #39222032
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Добавление в середину есть, но не быстрое. Похоже правда массив
 
тест
Код: 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.
			const Int32 TEST = 100000;
			Console.WriteLine("Вставка в конец");
			var sw = Stopwatch.StartNew();
			var l = new List<Int32>();
			for(Int32 i = 0; i < TEST; i++) {
				l.Add(i);
			}
			Console.WriteLine(sw.ElapsedMilliseconds);
			Console.WriteLine("Вставка предпоследним");
			sw = Stopwatch.StartNew();
			l = new List<Int32>();
			l.Add(0);
			l.Add(1);
			for(Int32 i = 2; i < TEST; i++) {
				l.Insert(i - 1, i);
			}
			Console.WriteLine(sw.ElapsedMilliseconds);
			Console.WriteLine("Вставка вторым");
			sw = Stopwatch.StartNew();
			l = new List<Int32>();
			l.Add(0);
			l.Add(1);
			for(Int32 i = 2; i < TEST; i++) {
				l.Insert(1, i);
			}
			Console.WriteLine(sw.ElapsedMilliseconds);


РезультатВставка в конец
0 мс
Вставка предпоследним
2 мс
Вставка вторым
1546 мс
...
Рейтинг: 0 / 0
22.04.2016, 08:46
| Ответить | Цитировать | Написать  
Реализация List<t>
    #39222049
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сон Веры Павловны
Участник
Dima TПохоже правда массив
Я же дал ссылку на исходник. Вот из потрохов реализации:
Код: c#
1.
private T[] _items;


Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
        public T this[int index] {
            get {
                // Following trick can reduce the range check by one
                if ((uint) index >= (uint)_size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException();
                }
                Contract.EndContractBlock();
                return _items[index]; 
            }
 
            set {
                if ((uint) index >= (uint)_size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException();
                }
                Contract.EndContractBlock();
                _items[index] = value;
                _version++;
            }
        }
...
Рейтинг: 0 / 0
22.04.2016, 09:06
| Ответить | Цитировать | Написать  
Реализация List<t>
    #39222056
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Сон Веры ПавловныDima TПохоже правда массив
Я же дал ссылку на исходник. Вот из потрохов реализации:
Код: c#
1.
private T[] _items;


Сразу не глянул. Извиняюсь.
...
Рейтинг: 0 / 0
22.04.2016, 09:13
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Реализация List<t>
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]