- 1
- 2
- 3
- 4
- 5
- 6
private List<string> _items
...
if (_items.Count <= 0)
return;-
C# / Говнокод #9201
+121
Запостил:
Alx,
23 Января 2012
Говнокод: по колено в коде.
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
© 2008-2024 «Говнокод.ру»
Обратная связь | Лицензионное соглашение | 
Follow us!
Follow us!
Count - это по времени в общем случае O(n)
if (!_items. GetEnumerator().MoveNext()) - это по времени всегда O(1)
Count - это по времени в общем случае O(n)
if (!_items.Any()) - это по времени всегда O(1)
хотя count может быть быстрее, если класс, реализующий List<> реализует быстрое свойство Count (например, чтение из переменной класса, а не через подсчет всех элементов), тогда компилятор сможет родить более быстрый код, чем через Any()
нужное подчеркнул
Хотя сейчас подумал, не факт что оно надежней (всякие переполнения, например).
Зачастую Listы - обертки над массивами. Там найти длину - быстро.
И ничего Майкрософт не измышлял. В шарпе индексы этих самых массивов - знаковые.
И как в вышеприведенном мною ГК из шарпов торчат уши портирования оных с явы.
В которой все примитивные типы, включая int тоже знаковые.
Хех, почитал msdn - чет новое узнал. Да, вобщем, не список это. Так же как в Яве, одно ни к чему не обязывающее название... вообще не понятно, зачем он тогда такой нужен, если есть Array. :)
Стандартный подход.
Кстати 6 человек плюсануло. А на мой вопрос
>в чем говно?
никто ответа не дал.
Хм. И снова цифра 6.
Интерфейсы позволяют получать "представление" одних коллекций в виде других. Или, например, можно реализовать список, содержащий 100 одинаковых элементов, реально храня лишь один элемент и размер списка, при этом все уже реализованные методы и функции будут для него прекрасно работать.
Кроме Лиспа списки существуют еще много где... это как бы не эзотерика. И это не вопрос древности, есть задачи которые лучше решаются с использованием списков, есть - массивов. А валить все в одну кучу - это все равно что вережки носками называть.
Приведу ещё пример: если вы решите реализовать ленивые списки, элементы которых вычисляются по мере необходимости, можно реализовать абстракцию списка , и вам не придётся писать кучу нового кода с алгоритмами для ленивых списков (как пришлось бы делать в Common Lisp, где нет ISeq абстракции из Clojure). Вы просто можете использовать весь код, потребляющий "Список" в качестве входных данных.
В CL такая абстракция не нужна - список, как и массив наследуют sequence. Все методы, которые специализируются на sequence будут работать для ленивой реализации, если она будет наследоваться от sequence.
Вот в этой книжке люди с воображением реализуют с помощью массива всё что угодно: связные списки, деревья, ассоциативные массивы, етц.
Там же можно найти описание АТД "Список", представленного в виде интерфейса в Java/C#.
List - это список. Нет, не тот список, что в Лиспе. Просто список! Список элементов, последовательность. Массив - последовательность элементов.
Вон в STL C++, то, что в C# называется List, назвали vector. Тоже не соответствует математическому понятию вектора. И ни чо, живём с этим.
в геометрическом смысле - не соответствует, а в алгебраическом - соответствует.
http://www.flowerbunker.ru/gorshechnye_rasteniya/katalog/catalog_id=1855.html
List тут не от лисповского списка, а скорее от гуишного ListBox.
http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx
КО: Нужный размер может быть заранее неизвестен.
Ваши слова выдают человека, который никогда не реализовывал списки\динамические массивы\деревья\хэштаблицы ручками на православных Pascal\C\Fortran.
Во-вторых, выбор реализации сильно зависит потребностей конкретной задачи. Добавление в начало массива - ещё более затратная операция, поскольку приходится двигать весь хвост в конец.
С другой стороны, обращение по индексу для такого массива будет очень быстрым.
Для этого и существуют различные реализации: используйте ту из них, которая наиболее подходит в каждом конкретном случае.
Часто читаете/пишете по индексу и редко добавляете в начало? ArrayList. Часто добавляете в начало\середину? LinkedList.
В большинстве случаев вполне хватает ArrayList'а. Кроме того, если есть догадки относительно требуемого размера, их можно сообщить конструктору и он изначально выделит достаточно большой буфер.
поэтому в языках, дающих сунуть пальцы сразу в пламенный мотор, массив, который суть непрерывная область памяти, занятая однотипными элементами, реаллоцируется либо сам по себе при вставке в конец (и тут как раз он сам решает, сколько ему приращивать, место под один элемент, или место равное половине существующей длины - может ты следующей операций тоже вставишь), либо не реаллоцируется, т.к. у него пока хватает свободного места - потому что объем этого самого свободного места умный программист сам прикинул и посоветовал массиву
я говорю о reserve в std::vector в c++, и это нормальная практика, когда массив самостоятельно растёт в 1.5 раза, если программист лично не выделил предварительно для него места - значит программиста всё устраивает
Есть логическое противоречие если пытаться заменить друг другом "последовательность", "список" и "массив". Последовательность не обязана быть конечной, может быть цикличной; последовательность не обязана содержать однотипные элементы. Массив - одна из разновидностей последовательности, которая не может быть бесконечной, не может быть цикличной, не может содержать разнородные элементы. Список - это другая разновидность последовательности, которая может быть бесконечной, цикличной и содержать разнородные элементы. Каким бы образом кто бы не использовал массив, нет возможности из него сделать список, т.как либо прийдется задействовать возможности списка для реализации списка (т.е. массив не может быть использован в качестве заменителя), либо все требования не будут соблюдены.
Слово "последовательность" я использую в математическом смысле, например, натуральный ряд это бесконечная последовательность натуральных чисел определенная через дискретную функцию 1+.
> Так программист может и не знать
Если программист не знает, значит для использования _массива_ ему нужны веские причины - такие, что минусы неоптимального роста будут приемлемы.
Если программист примерно предполагает конечный размер, он может руками сделать в нужном ему месте vec.reserve(vec.size() + additional) и не полагаться на x1.5 рост. Что есть для этого в дотнет - не знаю.
> Я говорю, что попытка сделать хороший динамический массив никогда не будет успешной. Но мало того, она никогда и не нужна.
В этом ты ошибаешься, иногда требуется одновременно и динамическое расширение, и O(1) для рандомного доступа, и уверенность в последовательном расположении элементов в памяти - например, прием пакета из сети, где конечная длина пакета становится известна только при получении первых N байт.
> вся остальная эзотерика о бесконечных последовательностях на конечных детерминированных железяках у тебя под столом и их именах
чего мне тут комментировать?
По поводу "железяк" - так факт их существования не делает способ по которому они работают правильным... если исходить из наличия фактов, то нужно принять несколько сотен религий как одновременно единственно верных, например.
Кроме того, нет никакой технической сложности в реализации бесконечных (циклических) списков, это не эзотерика никакая... Понажимай на TAB - вот тебе и циклический список...
Для того же примера с пакетами - можно отдельно прочитать заголовок, и отдельно содержание - а не выделять память наугад... как бы странный пример. Да и вообще, принять как данность, что не возможно одновременно O(1) и безразмерная коллекция. А пробовать объять необъятное...
Кроме того, я не правильно изначально записал, не Х * 1.5, а Х * 2.5, т.как "старый" массив - с ним уже особо нечего делать. Т.е. это еще кроме всего остального дефрагментация...
Заявлять, что динамические массивы не нужны, потому что я использую не голову, а абстракции в дотнете, не понимая как они устроены - это неправильно.
Ну и напоследок, АДТ "Список" таки можно выполнить с помощью структуры данных "массив". Каждый элемент хранит { T data, int next_offset }, т.е. хранит номер ячейки следующего элемента, где "-1" - нет следующего элемента. Что имеем - имеем интерфейс "списка", но (плюсы) располагаем все элементы кучно (и тем самым лучше кешируем данные), можем быстро рандомно перебрать все элементы (например, для поиска минимального), и (минусы) испытываем проблемы при неконтролируемом росте. В этом случае ты сможешь сделать даже свой любимый цикл в списке - просто запиши в хвостовой элемент оффсет не -1, а реальный - например, 0. Да, польза такой реализации вызовет больше вопросов, но как факт - она возможна.
Кстати, классический вопрос на собеседовании - как за O(N) определить цикличен ли односвязный список.
Если у вас вдруг такой большой массив, что «неиспользуемая память» становится критичной, будьте добры в самом начале посчитайте необходимый размер, иначе может получиться, что на массив размера Х + 1 памяти уже не хватит, хотя свободно на порядки больше — кусками по Х - 1, Х + 2, Х - 3,.. Фактически, массив на 33000 указателя может исчерпать всё адресное 32-битное пространство при такой стратегии. Такому капитану и в прапорщиках не задержаться.
Для таких целей в тайных лабораториях третьего рейха разрабатывают нлосоздают 64-битные операционные системы.
ArrayList - это практически реализация АДТ "List" на основе массива.
Интереса ради прочитал статью в википедии про списки. Уже с самого начала в статье есть странная неопределенность, где говорится о том, что понятия "список" и "последовательность" взаимозаменимы :S Ну мне остается только развести руками. Нет, понятия не взаимозаменимы, а "интерфейс" / описание АДТ которое там приводится - это описание последовательности, (да и то не совсем, почему-то автор посчитал нужным сообщить о том, что последовательность должна обязательно содержать однотипные элементы - при том, что нет такого требования), а не списка... но очевидно людей, которые так считают очень много, а убеждать кого-то, даже одного - хз да и незачем :)
Если после CL вы не принимаете определения, отличные от определений, принятых в CL, - это ваши проблемы.
бред
>в .NET есть ArrayList<T>
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html
http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html
since 1.2
>в .NET типы знаковые, в тех местах где знаковость не нужна
итд.
Продолжай жить дальше в своем уютном мелкомирке.
2 wvxvw
> один класс массива уже есть - зачем создавать еще один с путающим названием мне не понятно.
Вот тут я пас.
или ты запал на совпадение имен?
А вот здравого и резонного объяснения для таких моментов как
>в шарпе индексы массивов - знаковые.
>List<T>.Count заявлен как Int32 - т.е. знаковый
Объяснения, которое опровергнет моё утвержение о недопортировании с жабы я пока не что услышал.
Нет опровергающих фактов и логики тоже нет. Вместо них слышно жалкое шарпокукареканье - "бред".
Да, совпадения многих названия коллекций не случайны.
Все размеры в .NET - знаковые. Беззнаковые типы не входят в CTS - common type system, и некоторые языки под платформу .NET могут не понимать беззнаковые типы, не уметь с ними работать. Это для совместимости.
И неужто неизвестно, сколько проблем приносят в C/C++ беззнаковые типы? Именно в качестве size разных коллекций.
это такие структуры
http://msdn.microsoft.com/en-us/library/system.uint32.aspx