Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Соколиный глаз
C#
179 / 161 / 112
Регистрация: 25.07.2014
Сообщений: 2,870
Записей в блоге: 10
Завершенные тесты: 1
#1

Оптимальность кода по скорости выполнения

14.07.2018, 09:32. Просмотров 758. Ответов 5
Метки нет (Все метки)

Есть код:
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
using System;
using Examples.Collections;
 
namespace Examples.Collections.Generic
{
    //Односвязный линейный список.
    public class LinkedList<T> : IPrintable, ICloneableAs<LinkedList<T>>
    {
        #region Private Section
        #region Error Handlers
        private void TryThrowInvalidOperationException()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Односвязный линейный список пуст");
            }
        }
 
        private void TryThrowArgumentException(Node<T> target)
        {
            if (target == null)
            {
                throw new ArgumentException("Целевой узел равен null");
            }
        }
        #endregion Error Handlers
 
        private bool FindHelper(Node<T> node, T value)
        {
            return ((node != null) && (!node.Value.Equals(value)));
        }
 
        private Node<T> Find(T value)
        {
            Node<T> current = Head;
            while (FindHelper(current, value))
            {
                current = current.Next;
            }
            TryThrowArgumentException(current);
            return current;
        }
 
        private void Move(ref Node<T> first, ref Node<T> second)
        {
            first = second;
            second = second.Next;
        }
 
        private Node<T> FindPrevious(T value)
        {
            Node<T> previous = null;
            Node<T> current = Head;
            while (FindHelper(current, value))
            {
                Move(ref previous, ref current);
            }
            TryThrowArgumentException(current);
            return previous;
        }
 
        private void AddAfter(Node<T> target, T value)
        {
            Node<T> node = new Node<T>(value, target.Next);
            target.Next = node;
        }
        #endregion Private Section
 
        #region Public Section
        #region Properties
        public Node<T> Head { get; private set; }
        public Node<T> Tail { get; private set; }
        public int Count { get; private set; }
        #endregion Properties
 
        #region Interface Implementations
        public LinkedList<T> CloneAs()
        {
            LinkedList<T> result = new LinkedList<T>();
            Node<T> current = Head;
            while (current != null)
            {
                result.AddLast(current.Value);
                current = current.Next;
            }
            return result;
        }
 
        public object Clone() => CloneAs();
        #endregion Interface Implementations
 
        #region User Operations
        #region Add Operations
        public void AddFirst(T value)
        {
            Node<T> node = new Node<T>(value, Head);
            if (Count == 0)
            {
                Tail = node;
            }
            Head = node;
            Count++;
        }
 
        public void AddLast(T value)
        {
            Node<T> node = new Node<T>(value);
            if (Count == 0)
            {
                Head = node;
            }
            else
            {
                Tail.Next = node;
            }
            Tail = node;
            Count++;
        }
 
        public void AddBefore(T target, T value)
        {
            Node<T> previous = FindPrevious(target);
            if (previous == null)
            {
                AddFirst(value);
            }
            else
            {
                AddAfter(previous, value);
            }
            Count++;
        }
 
        public void AddAfter(T target, T value)
        {
            AddAfter(Find(target), value);
            Count++;
        }
        #endregion Add Operations
 
        #region Remove Operations
        public void RemoveFirst()
        {
            TryThrowInvalidOperationException();
            if (Count == 1)
            {
                Tail = null;
            }
            Head = Head.Next;
            Count--;
        }
 
        public void RemoveLast()
        {
            TryThrowInvalidOperationException();
            if (Count == 1)
            {
                Clear();
            }
            else
            {
                Node<T> previous = Head;
                while (previous.Next != Tail)
                {
                    previous = previous.Next;
                }
                previous.Next = null;
                Tail = previous;
                Count--;
            }
        }
 
        public void RemoveBefore(T value)
        {
            TryThrowInvalidOperationException();
            if (Count < 2)
            {
                TryThrowArgumentException(null);
            }
            if (Head.Next.Value.Equals(value))
            {
                Head = Head.Next;
            }
            else
            {
                Node<T> previous = Head;
                while ((previous.Next.Next != null) && !previous.Next.Next.Value.Equals(value))
                {
                    previous = previous.Next;
                }
                TryThrowArgumentException(previous.Next.Next);
                previous.Next = previous.Next.Next;
            }
            Count--;
        }
 
        public void RemoveAt(T value)
        {
            TryThrowInvalidOperationException();
            if (Head.Value.Equals(value))
            {
                RemoveFirst();
            }
            else
            {
                Node<T> previous = FindPrevious(value);
                previous.Next = previous.Next.Next;
                Count--;
            }
        }
 
        public void RemoveAfter(T value)
        {
            TryThrowInvalidOperationException();
            Node<T> current = Find(value);
            TryThrowArgumentException(current.Next);
            current.Next = current.Next.Next;
            Count--;
        }
 
        public void Clear()
        {
            Head = null;
            Tail = null;
            Count = 0;
        }
        #endregion Remove Operations
 
        public void Reverse()
        {
            if (Count < 2)
            {
                return;
            }
            Node<T> current = Head;
            while (current.Next != null)
            {
                Node<T> next = current.Next;
                current.Next = current.Next.Next;
                next.Next = Head;
                Head = next;
            }
            Tail = current;
        }
 
        public void Swap(int i, int j) // TODO: Подумать над возможной оптимизацией.
        {
            if (i == j)
            {
                return;
            }
            if (i > j)
            {
                Helper.Swap(ref i, ref j);
            }
          Node<T> previousFirst = null;
            Node<T> first = Head;
            var k = 0;
            while ((first != null) && (k < i))
            {
                Move(ref previousFirst, ref first);
                k++;
            }
            TryThrowArgumentException(first);
 
            Node<T> second = first;
            while ((second != null) && (k < j))
            {
                second = second.Next;
                k++;
            }
            TryThrowArgumentException(second);
 
            if (second == Tail)
            {
                Tail = first;
            }
 
            Node<T> nextSecond = second.Next;
            Node<T> last = first;
            while (last.Next != second)
            {
                last = last.Next;
            }
            
            second.Next = first;
            if (first.Next != second)
            {
                second.Next = first.Next;
            }
            
            if (previousFirst == null)
            {
                Head = second;
            }
            else
            {
                previousFirst.Next = second;
            }
            last.Next = first;
            first.Next = nextSecond;
        }
        #endregion User Operations
 
        #region Output Operations
        public override string ToString()
        {
            Node<T> current = Head;
            string result = $"LinkedList<{typeof(LinkedList<T>).GetGenericArguments()[0]}>: [";
            while (current != null)
            {
                result += current.ToString() + (current.Next != null ? Helper.Delimiter : "");
                current = current.Next;
            }
            result += ']';
            return result;
        }
 
        public void Print() => Console.Write(ToString());
 
        public void Println() => Console.WriteLine(ToString());
        #endregion Output Operations
 
        #region Operators
        #region Add Operators
        public static LinkedList<T> operator +(T value, LinkedList<T> target)
        {
            LinkedList<T> result = target.CloneAs();
            result.AddFirst(value);
            return result;
        }
 
        public static LinkedList<T> operator +(LinkedList<T> target, T value)
        {
            LinkedList<T> result = target.CloneAs();
            result.AddLast(value);
            return result;
        }
        #endregion Add Operators
 
        public static LinkedList<T> operator -(LinkedList<T> target, T value)
        {
            LinkedList<T> result = target.CloneAs();
            result.RemoveAt(value);
            return result;
        }
        #endregion Operations
        #endregion Public Section
    }
}
Вопрос следующий: насколько оптимален метод AddBefore? Смущает вызов AddFirst, так как там всегда проводится дополнительная проверка а пуст ли список, хотя для операции AddBefore всегда гарантируется, что в списке должен быть хотя бы 1 элемент. Следует ли избавиться от вызова AddFirst из-за этой:
C#
1
if (Count == 0)
проверки? Или в данном случае это вообще не критично?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2018, 09:32
Ответы с готовыми решениями:

Откуда такая разница в скорости выполнения кода?
Добрый день! Очень хочется понять, почему происходит следующее: Пишу код,...

Оптимизация скорости выполнения
Нахожусь в процессе написания проги для определения СЕО-параметров сайта....

Измерение времени выполнения кода
кто-нибудь может объяснить почему это не работает? using System; using...

Пояснить результат выполнения кода
Всем привет. Ребят, уже не первый раз сталкиваюсь с подобным, кто-нибудь...

Счетчик времени выполнения кода
Усердно читал на форуме темы по таймеру. Но так и не смог реализовать счетчик....

5
OwenGlendower
Супер-модератор
Эксперт .NET
9052 / 8003 / 3420
Регистрация: 17.03.2014
Сообщений: 15,823
Записей в блоге: 1
14.07.2018, 17:56 #2
Лучший ответ Сообщение было отмечено Volobuev Ilya как решение

Решение

Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
хотя для операции AddBefore всегда гарантируется, что в списке должен быть хотя бы 1 элемент.
Из кода это никак не следует. Никто не мешает создать экземпляр LinkedList и сразу вызвать AddBefore.

Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
Или в данном случае это вообще не критично?
Если необходима максимальная скорость, то избавляйся.
1
Соколиный глаз
C#
179 / 161 / 112
Регистрация: 25.07.2014
Сообщений: 2,870
Записей в блоге: 10
Завершенные тесты: 1
14.07.2018, 18:03  [ТС] #3
OwenGlendower, если будет попытка добавить перед элементом x (при условии что список пуст), то так как элемента x по просту не будет, FindPrevious выкинет исключение:
Unhandled Exception:
System.ArgumentException: Целевой узел равен null
at Examples.Collections.Generic.LinkedList`1[T].FindPrevious (T value) [0x0002d] in <39e2be4e103540378fce2151f5c57722>:0
at Examples.Collections.Generic.LinkedList`1[T].AddBefore (T target, T value) [0x00000] in <39e2be4e103540378fce2151f5c57722>:0
at Testing.MainClass.Main (System.String[] args) [0x00013] in <39e2be4e103540378fce2151f5c57722>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.ArgumentException: Целевой узел равен null
at Examples.Collections.Generic.LinkedList`1[T].FindPrevious (T value) [0x0002d] in <39e2be4e103540378fce2151f5c57722>:0
at Examples.Collections.Generic.LinkedList`1[T].AddBefore (T target, T value) [0x00000] in <39e2be4e103540378fce2151f5c57722>:0
at Testing.MainClass.Main (System.String[] args) [0x00013] in <39e2be4e103540378fce2151f5c57722>:0
Вообще я операции наподобие "вставить после/перед" делал так, чтобы в списке обязательно был хотя бы 1 элемент для выполнения этой операции.
0
OwenGlendower
Супер-модератор
Эксперт .NET
9052 / 8003 / 3420
Регистрация: 17.03.2014
Сообщений: 15,823
Записей в блоге: 1
14.07.2018, 18:14 #4
Лучший ответ Сообщение было отмечено Volobuev Ilya как решение

Решение

Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
если будет попытка добавить перед элементом x (при условии что список пуст), то так как элемента x по просту не будет, FindPrevious выкинет исключение:
Извиняюсь, невнимательно посмотрел. Однако плохо что исключение говорит что аргумент равен null, когда на самом деле список пуст. Это однозначно будет вводить в заблуждение.
1
Соколиный глаз
C#
179 / 161 / 112
Регистрация: 25.07.2014
Сообщений: 2,870
Записей в блоге: 10
Завершенные тесты: 1
14.07.2018, 18:23  [ТС] #5
OwenGlendower, спасибо за замечание, я подумаю как исправить.
0
TopLayer
768 / 569 / 300
Регистрация: 23.10.2016
Сообщений: 1,347
Завершенные тесты: 7
14.07.2018, 18:42 #6
Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
Или в данном случае это вообще не критично?
Вообще не критично. Строкой выше идёт создание объекта на куче, что будет происходить на порядок дольше. А вообще, тесты производительности можете сами произвести, когда "оптимизируете" код.
1
14.07.2018, 18:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2018, 18:42

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

Возможность продолжить выполнения кода
Здравствуйте. Постараюсь как можно понятней объяснить вопрос. Как можно в C#...

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru