Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
.NET 9

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

26.04.2025, 21:41. Показов 3468. Ответов 35
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ссылка. Разумеется, не по "чистому коду", а функционально. На самом деле я мог бы сделать и "традиционную" реализацию, это не очень сложно, но это привело бы к большому количеству косвенной рекурсии, которой я стараюсь избегать, так как сильно сомневаюсь, что компилятор оптимизирует ее (на самом деле там была бы не "чистая" косвенная рекурсия, которую как раз легко оптимизировать, предварительно преобразовав в прямую, а адская комбинация из прямой и косвенной рекурсии, когда каждая функция в паре вызывает как себя, так и другую) (и такая комбинация у меня уже была, я даже ввел goto, чтобы избавиться от этой "всенаправленной" рекурсии) (а как мы знаем, мои проекты и без такой рекурсии тормозят, нет смысла добавлять еще один тормоз там, где легко обойтись без него). Также на этом месте могла бы быть вообще реализация "в лоб", которая тоже раньше была у меня, но это еще бо́льшие тормоза из-за рекурсивного спуска на каждом элементе, а не по одному разу за ветку. Надеюсь, устранив лишние спуски и эту адскую рекурсию, я не ввел других тормозов или чего-то еще похуже?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.04.2025, 21:41
Ответы с готовыми решениями:

Приемлемо ли такое использование Visible в WPF?
Привет , начал изучение WPF сразу с практики , хочу сделать проверку логином и паролем перед входом...

Выбор обфускатора: сочетание бесплатности и приемлемого качества
Понимаю что много таких тем есть ,но ничего в них не могу понять какой нормальный обфускатор,и...

WCF метод должен вернуть приемлемый тип для dataGridView
Я не знаю как правильно оформить метод, чтобы он возвращал правильный тип, который на принимающей...

35
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38161 / 21096 / 4306
Регистрация: 12.02.2012
Сообщений: 34,683
Записей в блоге: 14
27.04.2025, 06:38
Etyuhibosecyu, в этом коде "без поллитры" не разберёшься... А в чем, собственно, состоит проблема? Есть два базовых алгоритма: прямой перебор и двоичный поиск. Для двоичного поиска в списке нужно обеспечить доступ к элементу по его индексу за фиксированное время (за O(1)). В противном случае двоичный поиск теряет смысл.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 08:22  [ТС]
Цитата Сообщение от Catstail Посмотреть сообщение
в этом коде "без поллитры" не разберёшься...
Конечно, специалист по Python и функциональному программированию в коде на C# не разберется...
Цитата Сообщение от Catstail Посмотреть сообщение
А в чем, собственно, состоит проблема?
Проблема в том, не несет ли такой код скрытые баги, тормоза или что-то еще подобное.
Цитата Сообщение от Catstail Посмотреть сообщение
Для двоичного поиска в списке нужно обеспечить доступ к элементу по его индексу за фиксированное время (за O(1)).
Для двоичного поиска в списке нужно сначала обеспечить, чтобы список был отсортирован.
Цитата Сообщение от Catstail Посмотреть сообщение
В противном случае двоичный поиск теряет смысл.
Не совсем, если доступ к элементу по его индексу за O(logn), то двоичный поиск будет за O(log2n), что все равно быстрее, чем O(n).

Добавлено через 8 минут
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
Конечно, специалист по Python и функциональному программированию в коде на C# не разберется...
Хотя согласен, даже специалист по C# разберется с трудом, если не он писал этот код, код не для начинающих.
0
Эксперт .NET
 Аватар для Usaga
14086 / 9303 / 1348
Регистрация: 21.01.2016
Сообщений: 34,926
27.04.2025, 09:20
Etyuhibosecyu, вопрос бессмысленный.

Приемлемо оно или нет определяется с помощью юнит-тестов и бенчмарков. Про оба этих механизма тебе уже миллион раз говорили. Показывали как с этим работать. Но «гении» они такие - любят работать абы как и советов не понимают
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38161 / 21096 / 4306
Регистрация: 12.02.2012
Сообщений: 34,683
Записей в блоге: 14
27.04.2025, 09:42
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
Хотя согласен, даже специалист по C# разберется с трудом, если не он писал этот код, код не для начинающих.
- ну, о чём я и говорю... Разобраться можно, но вряд ли у кого возникнет желание это делать. Тот, кто спрашивает, должен это понимать. И, поэтому, не предлагать копаться в коде, а четко сформулировать вопрос и привести кусок кода "в тему". Это - элементарная вежливость ТС
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 09:43  [ТС]
Цитата Сообщение от Catstail Посмотреть сообщение
И, поэтому, не предлагать копаться в коде, а четко сформулировать вопрос и привести кусок кода "в тему".
Там вроде как ссылка на конкретное место, начало метода IndexOfInternal() должно быть примерно посередине окна браузера.
0
 Аватар для IamRain
4693 / 2701 / 734
Регистрация: 02.08.2011
Сообщений: 7,226
27.04.2025, 10:39
Etyuhibosecyu, ага, а еще этот метод в окне браузера в масштабе 50% не помещатся на один экран.

Добавлено через 3 минуты
Вам уже сказали - надо самостоятельно написать бенчмарки, которые покрывают различные сценарии (fast path, slow path и прочее) и проверить.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 10:42  [ТС]
IamRain, да, ровно 100 строк. Я не подгонял, это случайность, которую я только сейчас обнаружил. У меня экран большой, если убрать заголовок и адресную строку (полноэкранный режим), в масштабе 100% как раз в точности помещается. Зато нет адской комбинации из прямой и косвенной рекурсии, которая вроде как приводит к тормозам, так как ее невозможно оптимизировать (это я так думаю).
0
Эксперт .NET
 Аватар для Usaga
14086 / 9303 / 1348
Регистрация: 21.01.2016
Сообщений: 34,926
27.04.2025, 10:45
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
которая вроде как приводит к тормозам
Ну можно же было два варианта метода написать, а потом сравнить в бенчмарке. Ты программист или смех на палочке? Все снимают метрики, один ты гадаешь...
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 11:01  [ТС]
Написал бенчмарк:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    [Benchmark]
    public void NaiveTest()
    {
        var length = 65536;
        var index = random.Next(list7.Length - length + 1);
        var n = random.Next(length);
        for (var i = 0; i < length; i++)
            if (bigList[index + i] == n)
            {
                _ = index + i;
                return;
            }
    }
 
    [Benchmark]
    public void ProgressiveTest()
    {
        var length = 65536;
        var index = random.Next(list7.Length - length + 1);
        var n = random.Next(length);
        _ = bigList.IndexOf(n, index, length);
    }

Даже если предположить, что "лишние" проверки при индексации отнимают половину времени (что маловероятно), у реализации по ссылке из шапки все равно остается ОГРОМНЫЙ запас преимущества в скорости.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 11:20  [ТС]
Написал бенчмарк специально на прямую и косвенную рекурсию:
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
    private double Direct(int x)
    {
        if (x <= 0)
            return 1;
        if (random.Next(2) == 1)
            return x * Direct(x - 1);
        else
            return x * Direct(x - 1);
    }
 
    private double Ping(int x)
    {
        if (x <= 0)
            return 1;
        if (random.Next(2) == 1)
            return x * Ping(x - 1);
        else
            return x * Pong(x - 1);
    }
 
    private double Pong(int x)
    {
        if (x <= 0)
            return 1;
        if (random.Next(2) == 1)
            return x * Ping(x - 1);
        else
            return x * Pong(x - 1);
    }
 
    [Benchmark]
    public void DirectTest()
    {
        Direct(100);
    }
 
    [Benchmark]
    public void IndirectTest()
    {
        Ping(100);
    }

Так что, мои догадки о тормозах подтвердились.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 11:28  [ТС]
IamRain, нет никаких ошибок в этих бенчмарках?
0
 Аватар для IamRain
4693 / 2701 / 734
Регистрация: 02.08.2011
Сообщений: 7,226
27.04.2025, 11:56
Etyuhibosecyu, я не знаю как работает твоя логика. Тебе скучно что-ли?
Возьми какой-нибудь опенсорс проект и поработай над ним - он тебя затянет, и будет что с кем обсуждать - сразу убьешь двух зайцев.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 12:11  [ТС]
Цитата Сообщение от IamRain Посмотреть сообщение
я не знаю как работает твоя логика. Тебе скучно что-ли?
Что нужно сделать, чтобы она стала более понятной, с учетом того, что разбить метод на части - неприемлемый вариант из-за тормозов? Добавить костыли в виде комментариев? Вынести содержимое if (low != null) в отдельный метод (там уже нет рекурсии)? Или что-то еще?

Добавлено через 5 минут
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
Вынести содержимое if (low != null) в отдельный метод (там уже нет рекурсии)?
К слову, это мысль. Вынес вот так, стало более понятно?
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
    private protected override MpzT IndexOfInternal(T item, MpzT index, MpzT length, bool fromEnd)
    {
        if (length == 0)
            return -1;
        if (low != null)
            return IndexOfTrivial(item, ref index, length, fromEnd);
        else if (high == null || highLength == null)
            throw new ApplicationException("Произошла серьезная ошибка при попытке выполнить действие. К сожалению, причина ошибки неизвестна.");
        var endIndex = index + length - 1;
        var bReversedOld = bReversed;
        if (bReversedOld)
        {
            Reverse();
            (index, endIndex) = (Length - 1 - endIndex, Length - 1 - index);
            fromEnd = !fromEnd;
        }
        try
        {
            var intIndex = highLength.IndexOfNotGreaterSum(index, out var bitsIndex);
            var endIntIndex = highLength.IndexOfNotGreaterSum(endIndex, out var endBitsIndex);
            while (endBitsIndex >= fragment)
            {
                endIntIndex++;
                endBitsIndex -= fragment;
            }
            if (intIndex != 0 && intIndex == highLength.Length && bitsIndex == 0 && highLength[intIndex - 1] != fragment)
            {
                intIndex--;
                bitsIndex = highLength[^1];
            }
            MpzT foundIndex;
            if (intIndex == endIntIndex)
            {
                foundIndex = high[intIndex].IndexOfInternal(item, bitsIndex, length, fromEnd);
                if (foundIndex >= 0)
                {
                    foundIndex += index - bitsIndex;
                    return bReversedOld ? Length - 1 - foundIndex : foundIndex;
                }
                return foundIndex;
            }
            MpzT offset;
            if (fromEnd)
            {
                offset = endIndex - endBitsIndex;
                foundIndex = high[endIntIndex].IndexOfInternal(item, 0, endBitsIndex + 1, true);
                if (foundIndex >= 0)
                    return bReversedOld ? Length - 1 - offset - foundIndex : offset + foundIndex;
                offset -= high[endIntIndex - 1].Length;
            }
            else
            {
                offset = index - bitsIndex;
                foundIndex = high[intIndex].IndexOfInternal(item, bitsIndex, high[intIndex].Length - bitsIndex, false);
                if (foundIndex >= 0)
                    return bReversedOld ? Length - 1 - offset - foundIndex : offset + foundIndex;
                offset += high[intIndex].Length;
            }
            for (var i = fromEnd ? endIntIndex - 1 : intIndex + 1;
                fromEnd ? i > intIndex : i < endIntIndex; i += fromEnd ? -1 : 1)
            {
                foundIndex = high[i].IndexOfInternal(item, 0, high[i].Length, fromEnd);
                if (foundIndex >= 0)
                    return bReversedOld ? Length - 1 - offset - foundIndex : offset + foundIndex;
                offset += fromEnd ? -high[i - 1].Length : high[i].Length;
            }
            if (fromEnd)
            {
                foundIndex = high[intIndex].IndexOfInternal(item, bitsIndex, high[intIndex].Length - bitsIndex, true);
                if (foundIndex >= 0)
                    return bReversedOld ? Length - 1 - offset - foundIndex : offset + foundIndex;
            }
            else
            {
                foundIndex = high[endIntIndex].IndexOfInternal(item, 0, endBitsIndex + 1, false);
                if (foundIndex >= 0)
                    return bReversedOld ? Length - 1 - offset - foundIndex : offset + foundIndex;
            }
            return -1;
        }
        finally
        {
            if (bReversedOld)
                Reverse();
        }
    }
 
    private protected virtual MpzT IndexOfTrivial(T item, ref MpzT index, MpzT length, bool fromEnd)
    {
        Debug.Assert(low != null);
        Debug.Assert(index < int.MaxValue - 1);
        Func<T, int, int, int> func = bReversed ^ fromEnd ? low.LastIndexOf : low.IndexOf;
        if (fromEnd)
        {
            index += length - 1;
        }
        if (bReversed)
        {
            var foundIndex = func(item, (int)(Length - 1 - index), (int)length);
            return foundIndex >= 0 ? Length - 1 - foundIndex : foundIndex;
        }
        else
            return func(item, (int)index, (int)length);
    }
0
Эксперт .NET
 Аватар для Usaga
14086 / 9303 / 1348
Регистрация: 21.01.2016
Сообщений: 34,926
27.04.2025, 12:16
IamRain, так вроде бы вопрос не предполагает анализ кода его. Если я правильно понял. Это он ссылку кинул. Но сам вопрос о поведении кода. А это тестами и бенчмарками и определяется.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 13:32  [ТС]
sau, вы раньше помогали мне разобраться в трудночитаемом коде, в этот раз не подскажете, нет ли тут СКРЫТЫХ багов и других проблем? СКРЫТЫЕ - это такие, которые простой проверкой в стиле Assert.AreEqual(microsoftList.IndexOf(index, length), bigList.IndexOf(index, length)) НЕ ПОКРЫВАЮТСЯ.
0
 Аватар для sau
2773 / 2073 / 386
Регистрация: 22.07.2011
Сообщений: 7,820
27.04.2025, 13:41
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
нет ли тут СКРЫТЫХ багов и других проблем? СКРЫТЫЕ - это такие, которые простой проверкой в стиле Assert.AreEqual(microsoftList.IndexOf(in dex, length), bigList.IndexOf(index, length)) НЕ ПОКРЫВАЮТСЯ.
- какой тут пример "скрытого бага" может быть , внешних зависимостей же нет ?
- если тестами все покрыто и все работает в соответствии с ожиданиями , ну тогда не знаю , разве что на утечку памяти проверить , переполнение стека.
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 179 / 41
Регистрация: 13.07.2017
Сообщений: 4,560
Записей в блоге: 14
27.04.2025, 14:11  [ТС]
Цитата Сообщение от sau Посмотреть сообщение
Если не покрываются , значит все функционирует как задумано ?
В простых случаях - да. А в каких-то особых - кто знает... Возможно, вы знаете, я же об этом и спрашиваю?

Добавлено через 17 минут
sau, простите, только сейчас увидел ваше отредактированное сообщение.
Цитата Сообщение от sau Посмотреть сообщение
- какой тут пример "скрытого бага" может быть , внешних зависимостей же нет ?
Ну что означает "решение откровенный костыль и несет скрытые баги и проблемы"? Какие-то в неочевидных ситуациях, наверное.
Цитата Сообщение от sau Посмотреть сообщение
- если тестами все покрыто и все работает в соответствии с ожиданиями , ну тогда не знаю , разве что на утечку памяти проверить , переполнение стека.
Ну, если в ветке всего 4 подветки, памяти практически безлимит, а стек 1 МБ, то не знаю...

Добавлено через 11 минут
sau, к слову, утечка памяти очень может быть. Через несколько минут прогона случайных операций с этими списками начинает потреблять 100 ГБ памяти и больше.
0
Эксперт .NET
 Аватар для Usaga
14086 / 9303 / 1348
Регистрация: 21.01.2016
Сообщений: 34,926
28.04.2025, 04:07
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
Через несколько минут прогона случайных операций с этими списками начинает потреблять 100 ГБ памяти и больше.
Ну и к чему опять задавать вопросы о скрытых багах, когда ты сам видишь баги не скрытые?..
0
Заблокирован
28.04.2025, 22:36
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
начинает потреблять 100 ГБ памяти и больше.


А до прогона сколько?

Это что за список в котором нужно рекурсивно искать то?

Добавлено через 4 минуты
Цитата Сообщение от sau Посмотреть сообщение
разве что на утечку памяти проверить
У шарпистов бывают утечки памяти?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
28.04.2025, 22:36
Помогаю со студенческими работами здесь

Является ли это приемлемой практикой?
class Company { public static Company CurrentCompany; public List&lt;Worker&gt; Workers =...

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

Реализация функции вычисления электронно-цифровой подписи RSA. Реализация функции проверки ЭЦП RSA
Последовательность выполняемых действий включает следующие шаги. 1. Сформировать два простых числа...

Binding списка объектов из другого списка объектов списка
Добрый день. В приложении есть список объектов, в каждом из которых есть ещё список объектов с...

Работа со списком, поиск элемента в списке по параметрам элемента в списке, удаление одинаковых и изменение существующих
Всем привет! Есть такая проблема, не могу обработать список. Мне нужно перебрать список, в нем...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru