Приемлема ли такая реализация поиска в списке?

@Etyuhibosecyu · Регистрация: 13.07.2017

Студворк — интернет-сервис помощи студентам

Ссылка. Разумеется, не по "чистому коду", а функционально. На самом деле я мог бы сделать и "традиционную" реализацию, это не очень сложно, но это привело бы к большому количеству косвенной рекурсии, которой я стараюсь избегать, так как сильно сомневаюсь, что компилятор оптимизирует ее (на самом деле там была бы не "чистая" косвенная рекурсия, которую как раз легко оптимизировать, предварительно преобразовав в прямую, а адская комбинация из прямой и косвенной рекурсии, когда каждая функция в паре вызывает как себя, так и другую) (и такая комбинация у меня уже была, я даже ввел goto, чтобы избавиться от этой "всенаправленной" рекурсии) (а как мы знаем, мои проекты и без такой рекурсии тормозят, нет смысла добавлять еще один тормоз там, где легко обойтись без него). Также на этом месте могла бы быть вообще реализация "в лоб", которая тоже раньше была у меня, но это еще бо́льшие тормоза из-за рекурсивного спуска на каждом элементе, а не по одному разу за ветку. Надеюсь, устранив лишние спуски и эту адскую рекурсию, я не ввел других тормозов или чего-то еще похуже?

@sau · 28.04.2025, 23:19

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

У шарпистов бывают утечки памяти?

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

Добавлено через 9 минут

if (!(high != null && highLength != null && destination.high != null && destination.highLength != null))
throw new ApplicationException("Произошла серьезная ошибка при попытке выполнить действие. К сожалению, причина ошибки неизвестна.");

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

@Etyuhibosecyu · 28.04.2025, 23:30 **[ТС]**

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

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

Спасибо за напоминание, я в целом знаю, что нужно использовать using и вызывать Dispose(), но конкретно в данном случае не вспомнил. Постараюсь выбрать время и исправить.

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

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

Это чисто формальное условие, чтобы компилятор не ругался на "использование вероятной пустой ссылки" (не точная цитата). По факту когда включается high, low обнуляется и наоборот. Разве что если многопоточно вызывать методы добавления и удаления, теоретически можно словить такое исключение. Но класс изначально не потокобезопасный.

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

класс в несколько тысяч строк точно нуждается в декомпозиции

В декомпозиции на что? Это же одна логическая сущность.

@sau · 28.04.2025, 23:57

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

В декомпозиции на что? Это же одна логическая сущность.

всегда есть на что порезать , ну или хотя бы по partial-ам разнести концептуально близкие блоки.
а так , например , если у Вас полно функций из нескольких слов , по типу IncreaseCapacityLinear , IncreaseCapacityExponential ... то это уже сущность размытая , которую можно вынести , далее всякие мат.операции можно оформить в какой нибудь Math.Collection , валидаторы-верификаторы унифицировать и вынести так же отдельно , все что internal - тоже отдельные сервисы и т.п.

Добавлено через 7 минут
И комментарии , сейчас человек со стороны посмотрит и ужаснется , этот код никто и никогда не захочет взять дорабатывать , вникать - просто окинув его взглядом хочется сразу закрыть.
плюс это так же полезно для выявления скрытых сущностей, ибо когда будете комментировать назначения внутренних блоков , задумываясь над смыслом происходящего , то сразу увидите зависимости которые могут быть оформлены отдельным классом.
А еще попробуйте юнит.тесты пописать не только на паблик , но и на внутренние методы , у Вас ничего не выйдет , потому что что бы его дернуть , нужно черт его знает что и где настроить , появится желание это упростить и будет понятно что именно нужно отрефакторить.

@Wolfdp · 29.04.2025, 04:44

C#
1
2
if (!(high != null && highLength != null && destination.high != null && destination.highLength != null))
throw new ApplicationException("Произошла серьезная ошибка при попытке выполнить действие. К сожалению, причина ошибки неизвестна.");

Ужс.... ну вот зачем вы мне это показали? У меня же теперь паника.

Отдельно замечу что кроме фантастической "читаемости" этого кода, в момент отлова проблемы у нас есть 25% шанс угадать что в тот момент было null. Ещё и ApplicationException... Ощущается как "сгорел сарай, гори и хата".

Если это входные аргументы, то нужно делать что-то в таком духе

C#
1
2
3
4
ArgumentNullException.ThrowIfNull(high);
ArgumentNullException.ThrowIfNull(highLength);
ArgumentNullException.ThrowIfNull(destination.high, $"{nameof(destination)}.{nameof(destination.high)}");
ArgumentNullException.ThrowIfNull(destination.highLength, $"{nameof(destination)}.{nameof(destination.highLength)}");

Так хотя бы можно будет увидить что именно было некоректным.

Если это просто локальные переменные.... Ну блин не знаю, кажись отсутствие метода расширения у NullReferenceException должен намекать что Nullable reference types существует не просто так и нужно проверять на null и обращать внимание на warning.

@Etyuhibosecyu · 29.04.2025, 14:22 **[ТС]**

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

в момент отлова проблемы у нас есть 25% шанс угадать что в тот момент было null.

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

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

Ещё и ApplicationException... Ощущается как "сгорел сарай, гори и хата".

Поясните для тех, кто "не в теме". Чем-то плохое исключение ApplicationException?

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

Если это входные аргументы

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

Если это просто локальные переменные

Ни то, ни другое, это поля этого класса, они объявлены вверху.

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

Ну блин не знаю, кажись отсутствие метода расширения у NullReferenceException должен намекать что Nullable reference types существует не просто так и нужно проверять на null и обращать внимание на warning.

Еще раз:

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

Это чисто формальное условие, чтобы компилятор не ругался на "использование вероятной пустой ссылки" (не точная цитата). По факту когда включается high, low обнуляется и наоборот.

Добавлено через 1 час 53 минуты
sau, разбил на два файла, слегка изменил текст исключения, добавил комментарии там, где они не "капитанские", добавил Dispose() (по факту получилось добавить только в одном месте при уменьшении емкости, в остальных случаях внутренние списки нужны). Так лучше?

@sau · 29.04.2025, 22:14

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

добавил комментарии там, где они не "капитанские"

if (length == 0) // Если длина копируемой последовательность ноль, то ничего делать не надо.
return; - вот это как раз капитанский коммент , и практически бесполезный , из самого определения понятно что если 0 то возвращаемся , но это не раскрывает сути происходящего , комментарий должен объяснять «почему», а не «что».

допустим функция CopyToInternal - из названия понятно , что какое-то внутренне копирование чего-то куда-то , но в самом теле куча каких-то проверок/условий , глядя на которые не понять почему они тут и что вообще происходит , почему там какой-то реверс - это все требует погружения в какой-то контекст , было бы неплохо в summary более развернуто указать целевое назначение функции , если она реализует какой-то стандартный алгоритм - можно ссылочку на RFC доку оставить , ну и для каждого IF-ELSE блока в кратце пояснить какую задачу он решает , иначе это просто какой-то ассемблер по факту: intIndex , bReversed , ignoreReversed , sourceIndex = Length - length - sourceIndex; - ничерта непонятно , набор ничего не говорящих переменных и каких-то манипуляций с ними. (Capacity тоже выглядит страшно)

Ладно , допустим я просто не в теме , но представим что Вы уволились/пропали , и кто-то должен будет разобраться в этом коде , вопрос как ? , - сами-то , в целом , предполагаете что это возможно ?
Если посмотрите на , скажем , какие-то более менее известные библиотеки на гитхабе . то я видел примеры , где в начале файла целая история про сам файл , и к каждой функции описание больше чем сама функция , и не скажу что это плохо , во всяком случае в подобном коде это точно лишним не будет , т.к иначе его не понять.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
var this2 = (TCertain)this;
            ArgumentOutOfRangeException.ThrowIfLessThan(value, Length);
            if (value == _capacity)
                return;
            if (parent != null && value > parent.fragment)
                value = parent.fragment;
            if (value == 0)
            {
                low = new();
                high = null;
                highLength = null;
            }
            else if (value <= LeafSize)
            {
                if (high != null && highLength != null)
                    ReduceCapacityExponential(LeafSize);
                if (high != null && highLength != null)
                    Compactify();
                var first = this;
                for (; first.high != null; first = first.high[0], first.parent?.high?.Dispose())
                {
                    Debug.Assert(first.highLength != null);
                    first.high.Skip(1).ForEach(x => x.Dispose());
                    first.highLength.Dispose();
                }
                Debug.Assert(first.low != null);
                low = first.low;
                var value2 = (int)value;
                low.Capacity = value2;
                high = null;
                highLength = null;
            }
            else if (low != null)
            {
                fragment = (MpzT)1 << (GetArrayLength((value - 1).BitLength - LeafSizeBitLength,
                    SubbranchesBitLength) - 1) * SubbranchesBitLength + LeafSizeBitLength;
                while (fragment << SubbranchesBitLength < value)
                    fragment <<= SubbranchesBitLength;
                var highCount = (int)GetArrayLength(value, fragment);
                high = new(highCount);
                for (MpzT i = 0; i < value / fragment; i++)
                {
                    high.Add(CapacityCreator(fragment));
                    high[^1].parent = this2;
                }
                if (value % fragment != 0)
                {
                    high.Add(CapacityCreator(value % fragment));
                    high[^1].parent = this2;
                }
                var preservedLow = low;
                low = null;
                Length = 0;
                var first = this;
                for (; first.high != null; first = first.high[0])
                    first.highLength = [preservedLow.Length];
                ArgumentNullException.ThrowIfNull(first.low);
                first.low.AddRange(preservedLow);
                if (preservedLow.Length != 0)
                    first.Length = preservedLow.Length;
            }
            else if (high != null && highLength != null)
            {
                var newFragment = (MpzT)1 << (GetArrayLength((value - 1).BitLength - LeafSizeBitLength,
                    SubbranchesBitLength) - 1) * SubbranchesBitLength + LeafSizeBitLength;
                while (newFragment << SubbranchesBitLength < value)
                    newFragment <<= SubbranchesBitLength;
                if (newFragment > fragment)
                    IncreaseCapacityExponential(value, newFragment);
                else if (newFragment < fragment)
                {
                    ReduceCapacityExponential(newFragment);
                    AddCapacity((fragment << SubbranchesBitLength) - _capacity);
                    ReduceCapacityLinear(value);
                }
                else if (value > _capacity)
                    IncreaseCapacityLinear(value);
                else
                    ReduceCapacityLinear(value);
            }
            AddCapacity(value - _capacity);
#if VERIFY
            if (high != null && highLength != null)
                Debug.Assert(Length == highLength.ValuesSum && Length == high.Sum(x => x.Length));
            Verify();
#endif

@Wolfdp · 30.04.2025, 06:57

Если это в отладчике, то можно взять и посмотреть

Ага, проходил уже через это. Выливаешь код в релиз, тепер приходит issue "не работает, выводить ошибку AppException с текстом âåòð³øíÿ ïîìèëêà çàñòîñóíêó". И тут понимаешь что использовать кириллицу и обобщенные исключения -- не самая светлая мысль.

Дело ваше, можете не расписывать. Не мне потом угадывать откуда прилетел баг. В целом глядя на россыпь high != null && highLength != null выглядит как будто есть смысл в первую очередь применить совет от sau, и декомпозировать код, чтобы временный элемент содержал логику внутри себя и не нужно было делать 100500 проверок на null.

@belalugoci · 30.04.2025, 07:59

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

В целом глядя на россыпь high != null && highLength != null выглядит как будто есть смысл в первую очередь применить совет от sau, и декомпозировать код, чтобы временный элемент содержал логику внутри себя и не нужно было делать 100500 проверок на null.

для меня актуальная тема, подскажите тогда как правильно это делать? ведь вынос проверок внутрь объекта не избавит вас от проверок - просто поменяется место где это происходит, причем в том месте откуда вы всё убрали придется всё равно делать проверку, просто это будет не null, а код ошибки или bool. Или я что-то не понимаю?

@Wolfdp · 30.04.2025, 08:30

как правильно это делать?

Сам бы хотел иметь чёткий список правил "когда и что инкапсулировать". Грубо говоря у нас есть десяток массивов, которые в моменте создаем для чего либо. Если логика подразумевает что все массивы создаются сразу и по отдельности не применяются -- пакуем в объект, и прописываем методы взаимодействия с ним, где нет этих проверок на null, т.к. у нас единая проверка на то что есть/нет этот объект на верхнем уровне кода.

Основная трудность -- выделить этот самый скоп для инкапсулирования. Когда пишешь в моменте, то тыкнуть new|dispose|null можно в любой момент и поначалу так и строчишь. А потом осознаешь, что на строчку кода у тебя десять проверок на null.

@belalugoci · 30.04.2025, 14:06

Wolfdp, я немного не про это. Вот нет у вас проверки на null, вроде всё хорошо, но как вы узнаете сработает код или нет? Вы все равно поставите проверку, только она будет не if (aaa != null), а будет if (!dbObject.aaaIsNull()).

@Usaga · 30.04.2025, 16:09

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

Вот нет у вас проверки на null, вроде всё хорошо, но как вы узнаете сработает код или нет?

Юнит-тесты.

@SmallEvil · 30.04.2025, 16:17

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

Вот нет у вас проверки на null, вроде всё хорошо, но как вы узнаете сработает код или нет? Вы все равно поставите проверку,

Суть в том где будет эта проверка.
В одном месте, там где это необходимо, или нигде, если в этом нет нужды, или эти проверки будут на каждом уровне, что излишне и затратно.
Уровни, это уровни абстракции, включая отношения вызываемый<->вызывающий код.

Одного "тормоза" уже написали, С#, со всем что нужно и не нужно.
Теперь что, "тормоз" над "тормозом"? Утрировано. Это я про сурс этой темы.

@belalugoci · 30.04.2025, 17:19

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

Юнит-тесты.

а причем тут юнит-тесты? речь про определение null.

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

Суть в том где будет эта проверка

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

простой пример, у вас есть например двухсвязный список

C#
1
2
3
4
5
6
class List
{
    List prev {get; set}
    List next {get; set}
    int value {get; set}
}

вы пишете

C#
1
2
3
4
List M = new List();
// тут заполняете его чем-то и у вас появляется переменная first указывающая на начало списка
var cur = first;
while (cur.next != null) cur = cur.next;

как вы избавитесь от проверки при обходе списка?
Несомненно можно написать методы IsLast() или GotoLast() и получить нужный результат, но так вы просто условие перекинули в другое место кода. Об этом речь?

@SmallEvil · 30.04.2025, 17:56

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

как вы избавитесь от проверки при обходе списка?

Там где нужно, от проверок не избавится.
Но там где можно написать код без проверок, написав контракт что входные данные будут в априори валидные, можно и нужно. Оставить проверки на вызывающий код, конечно, если это приемлемо.
Не знаю что там за 4 проверки в коде ТС, но это перебор.
Учитывая что у него есть какой то length.

А по вашему примеру, вот вариант:

C++
1
2
3
4
int size = list.size();
node* h = list.first();
while(size--)
   h = h->next;

Классика жанра. Вот почему в большинстве контейнеров держать этот size/length.
Когда мы берем у списка first, мы же не проверяем на nullptr и не кричим во всю глотку, аларм, там же nullptr!? Нет.

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

@Wolfdp · 30.04.2025, 18:42

Идея не в том чтобы наглухо избавится от проверки, а чтобы:
- делать её в одном месте для одного объекта. Т.е. вместо километрового is null для 100500 полей чекаем единый объект и пляшем от него
- логика работы с полями переносится в этот объект, где эта проверка не нужна. Т.е. даже поля не нужно делать null, что резко упрощает код и IDE перестает лишний раз паниковать.

Я выше писал что нет универсального правила когда нужно паковать это добро, а когда нет. У ТСа в коде вроде парой ходят значения high и highLength, так что допускаю что там есть возможность запаковки в что-то единое.

Пример с элементом направленного списка не совсем про это. Пустое свойство Next как бы валидно и имеет логическое значение что это "end". Я же скорее говорил про случай когда есть набор значений, которые либо все сразу существуют, либо все null, и третьего состояния не должно быть.

---------

Мне сейчас с головы сложно дать хороший пример прям из практики. Обычно если поле допускает null, то это штатная ситуация и просто идем по другой ветке кода (как с направленным списком). Если нужно просто временно что-то куда-то сохранить, то прям в методе создается переменная и это не пихается в поля.

@belalugoci · 30.04.2025, 19:19

SmallEvil, Wolfdp, понял, спс

Новые блоги и статьи Все статьи Все блоги /
сукцессия 30. Фосфорный и азотный замки по "честному" закону лимитирования Либиха anaschu 16.07.2026 Основные достижения за последние дни 1. Механизм отложенного высвобождения фосфора Добавлен специальный пул для медленного разложения меланизированных гиф ЕСМ Реализована разная скорость. . .	Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .	Как надо было делать правильно - вообще не слушать ИИ, его дело - текст. Hrethgir 15.07.2026 А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её. Всё это стресс конечно. Почему?. . .	Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет
Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .	сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .

@Etyuhibosecyu Труд вопреки насмешкам 363 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,829 Записей в блоге: 14

	.NET 9 Приемлема ли такая реализация поиска в списке? 26.04.2025, 21:41. Показов 3634. Ответов 35 Метки нет (Все метки) Ссылка. Разумеется, не по "чистому коду", а функционально. На самом деле я мог бы сделать и "традиционную" реализацию, это не очень сложно, но это привело бы к большому количеству косвенной рекурсии, которой я стараюсь избегать, так как сильно сомневаюсь, что компилятор оптимизирует ее (на самом деле там была бы не "чистая" косвенная рекурсия, которую как раз легко оптимизировать, предварительно преобразовав в прямую, а адская комбинация из прямой и косвенной рекурсии, когда каждая функция в паре вызывает как себя, так и другую) (и такая комбинация у меня уже была, я даже ввел goto, чтобы избавиться от этой "всенаправленной" рекурсии) (а как мы знаем, мои проекты и без такой рекурсии тормозят, нет смысла добавлять еще один тормоз там, где легко обойтись без него). Также на этом месте могла бы быть вообще реализация "в лоб", которая тоже раньше была у меня, но это еще бо́льшие тормоза из-за рекурсивного спуска на каждом элементе, а не по одному разу за ветку. Надеюсь, устранив лишние спуски и эту адскую рекурсию, я не ввел других тормозов или чего-то еще похуже? 0

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	30.04.2025, 14:06
	Wolfdp, я немного не про это. Вот нет у вас проверки на null, вроде всё хорошо, но как вы узнаете сработает код или нет? Вы все равно поставите проверку, только она будет не `if (aaa != null)`, а будет `if (!dbObject.aaaIsNull())`. 0

@Wolfdp 3790 / 1767 / 371 Регистрация: 15.06.2012 Сообщений: 6,543 Записей в блоге: 3
	30.04.2025, 18:42
	Идея не в том чтобы наглухо избавится от проверки, а чтобы: - делать её в одном месте для одного объекта. Т.е. вместо километрового is null для 100500 полей чекаем единый объект и пляшем от него - логика работы с полями переносится в этот объект, где эта проверка не нужна. Т.е. даже поля не нужно делать null, что резко упрощает код и IDE перестает лишний раз паниковать. Я выше писал что нет универсального правила когда нужно паковать это добро, а когда нет. У ТСа в коде вроде парой ходят значения high и highLength, так что допускаю что там есть возможность запаковки в что-то единое. Пример с элементом направленного списка не совсем про это. Пустое свойство Next как бы валидно и имеет логическое значение что это "end". Я же скорее говорил про случай когда есть набор значений, которые либо все сразу существуют, либо все null, и третьего состояния не должно быть. --------- Мне сейчас с головы сложно дать хороший пример прям из практики. Обычно если поле допускает null, то это штатная ситуация и просто идем по другой ветке кода (как с направленным списком). Если нужно просто временно что-то куда-то сохранить, то прям в методе создается переменная и это не пихается в поля. 0

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	30.04.2025, 19:19
	SmallEvil, Wolfdp, понял, спс 0