- при небольших значениях M и N все эти прикидки не работают. Как Вы знаете, например, линейный поиск в массиве из трех элементов, скорее всего, будет не медленнее, а быстрее, чем метод половинного деления.
- В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов.
- собственно говоря, никто не утверждал, что внутри очередь организована как массив. Если мне известно заранее число различных приоритетов (а оно, как правило, известно и невелико), то вставка обьекта происходит даже не за O(m), а за O(1) - а как это реализовать, не очень важно, например, так, как Вы сказали.
- и самое главное - совершенно не факт, что вставление и удаление из очереди - то место кода, которое надо оптимизировать :)
Использование приоритета как одного из аргументов важно, на мой взгляд, не для того, чтобы немедленно начать думать о деталях реализации, а скорее для того, чтобы напоминать разработчику, что обьекты МОГУТ ИМЕТЬ РАЗЛИЧНЫЙ приоритет. Чтобы он непрерывно об этом помнил и учитывал в своем дизайне. Пусть даже в 99% случаев этот приоритет игнорируется.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
Re:
Date: 2003-05-29 01:26 pm (UTC)- при небольших значениях M и N все эти прикидки не работают. Как Вы знаете, например, линейный поиск в массиве из трех элементов, скорее всего, будет не медленнее, а быстрее, чем метод половинного деления.
- В случае, когда у меня высокоприоритетных обьектов существенно меньше, чем низкоприоритетных, время их вставки в очередь будет не O(logN), а O(K), где K - количество высокоприоритетных обьектов.
- собственно говоря, никто не утверждал, что внутри очередь организована как массив. Если мне известно заранее число различных приоритетов (а оно, как правило, известно и невелико), то вставка обьекта происходит даже не за O(m), а за O(1) - а как это реализовать, не очень важно, например, так, как Вы сказали.
- и самое главное - совершенно не факт, что вставление и удаление из очереди - то место кода, которое надо оптимизировать :)
Использование приоритета как одного из аргументов важно, на мой взгляд, не для того, чтобы немедленно начать думать о деталях реализации, а скорее для того, чтобы напоминать разработчику, что обьекты МОГУТ ИМЕТЬ РАЗЛИЧНЫЙ приоритет. Чтобы он непрерывно об этом помнил и учитывал в своем дизайне. Пусть даже в 99% случаев этот приоритет игнорируется.