|
|
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
AlexandrPlusvinoAlexandrPlus[quot vino][quot AlexandrPlus]...так и в этой другого N не может быть... здесь как раз N <= M и только поиском можно найти искомое число тады, чтобы приладить алгоритм - можно расширить массив N до M+1, заполнив нулями, и когда в m[0] или по порядку следования в m встретится 0, то просто брать в m[0] следующие число по порядку ОДНОГО прохода по m при этом остаемся в "линейном" времени P.S. Хотя есть память ограничена, то - не пройдет. вот-вот, поэтому и нужна БИТОВАЯ карта, ее размер будет минимален перестановка, на самом деле, не считается дешевой операцией, и к тому же Вы захотели дополнительное условие проверять (на =0) а то,что выделено, может привести к зацикливанию ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:32:53 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
AlexandrPlus...можно расширить массив N до M+1, заполнив нулями, и... вот главная идея - тогда, похоже, можно применить расчетную формулу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:38:13 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
точнее, я глюканул, - там же не будет последовательности ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:40:47 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
Очень юный падаван пишет: > Случайно к вам попал =) > Но прям даже интересно стало. А как оцените такой код? Это джава, Это хренотень какая-то а не джава. Ну да ладно. Должно быть что-то типа Код: plaintext 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. Код: plaintext Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:43:32 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
> Очень юный падаван > if((s = set.size()) == size){ > doubleValue = array[i]; > break; Вот я и не понял, при чём тут размер какой-то. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:44:46 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
junior idiot пишет: > такие ситуации обычно и возникают, потому и написали "линейное", но это > нифига не значит что миллион любых чисел можно так взять и вставить в > этот хешсет так же быстро как в массив. Время -- линейное, но алгоритм не обладает в общем случае статистической устойчивостью. Т.е. иногда может срываться. Хорошо, что ты кстати это знаешь. Многие тупо думают что скорость поиска в хэш-таблице - строго константа. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:47:05 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
Можно обратиться к массиву как к таблице через соответствующий SQL запрос. Можно вместо массива использовать тот же словарь из библиотеки scripting (он не пропустит дупликат).... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:50:59 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
MasterZiv > Очень юный падаван > if((s = set.size()) == size){ > doubleValue = array[i]; > break; Вот я и не понял, при чём тут размер какой-то. как я понял - если размер множества не изменился, то последнее вставленное число в нем уже было. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 16:52:31 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
vinoAlexandrPlusvinoAlexandrPlus[quot vino][quot AlexandrPlus]...так и в этой другого N не может быть... здесь как раз N <= M и только поиском можно найти искомое число тады, чтобы приладить алгоритм - можно расширить массив N до M+1, заполнив нулями, и когда в m[0] или по порядку следования в m встретится 0, то просто брать в m[0] следующие число по порядку ОДНОГО прохода по m при этом остаемся в "линейном" времени P.S. Хотя есть память ограничена, то - не пройдет. вот-вот, поэтому и нужна БИТОВАЯ карта, ее размер будет минимален перестановка, на самом деле, не считается дешевой операцией, и к тому же Вы захотели дополнительное условие проверять (на =0) а то,что выделено, может привести к зацикливанию Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. ничего не зацикливается - и один проход (i) перестановка (изменение указателей) вообще не дешевая, но речь идет о "математическом" времени ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 17:06:49 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
VladConnМожно обратиться к массиву как к таблице через соответствующий SQL запрос. В "математическом" времени SQL-запрос в общем случае - комбинаторный перебор ведь, да ещё будет декартово произведение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 17:26:03 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
AlexandrPlus Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. один проход - слишком оптимистично сказано, так как ячейки, наполненные нулями, тоже начнут проверяться, а это уже не N ячеек ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 17:31:04 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
Зив, а чем принципиально с точки зрения скорости работы отличается твой код на жабе от такой простой лабуды: Код: plaintext 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. Ну понятно, твой HashTable будет занимать меньше места в памяти. Ну ты вроде на память забил и делал упор на быстродействие. Так этот вариант ещё и побыстрее будет, бо хэши то вычислять нэ трэба... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 18:39:22 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
miksoft пишет: > как я понял - если размер множества не изменился, то последнее > вставленное число в нем уже было. Вау, какие полёты мыслей ! А я и недопёр ! А по-простому нельзя было ? Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 18:58:46 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
mikhail_n пишет: > Зив, а чем принципиально с точки зрения скорости работы отличается твой > код на жабе от такой простой лабуды: В общем-то ничем, если не учитывать, что твой код не работает (не инициализируется массив buffer[M]). А так -- массив -- частный случай хэш-таблицы. Только памяти жрёт больше, как ты и заметил. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 19:01:58 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
vinoAlexandrPlus, очевидно, что когда N = M+1, задача вырождается в расчетную: искомое число = сумма элементов -сумма арифметической последовательности (1,2,..,M) А мне подумало - вспоминая то, когда в ВУЗе программировали голые процессоры - программа из 0 и 1: то есть программируя, невольно думаешь как машина Тьюринга - вычисления гораздо более затратны, чем сравнения ячеек и смещения с ячейки на ячейку. А генетические алгоритмы - для задач оптимизации оказываются более эффективны, чем расчетные. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.07.2009, 21:32:16 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
alusovПодскажите правильный алгоритм. Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно число в этом массиве повторяется два раза. Как найти число за наименьшее время. Хм... По-моему, условие несколько неполное. Не раскрыто какие вспомогательные структуры данных разрешается использовать массивы, множества, либо, вообще, задача должна быть решена "на месте" без затрат памяти, т.е. используя только исходные данные ну и миниум переменных(индексы, буфер и прочее). В случае решения "на месте" думаю только сортировка поможет... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 03:33:06 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
грешок есть Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 05:43:14 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
MasterZiv Вау, какие полёты мыслей ! А я и недопёр ! А по-простому нельзя было ? Ну, мы уже выяснили, что на добавление уходит время, зависящее от количества элементов. Думаю, что время поиска элемента имеет ту же зависимость. А вот проверка размера, имхо, есть операция по времени фиксированная и более дешевая =) Собственно, руководствовался только этими соображениями. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 12:00:35 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
Очень юный падаван пишет: > Ну, мы уже выяснили, что на добавление уходит время, зависящее от > количества элементов. Думаю, что время поиска элемента имеет ту же Во-первых, вставка в хеш-таблицу -- те же O(1). Во-вторых, тебе вставлять-то в таблицу всё равно надо. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 12:42:58 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
MasterZiv Во-первых, вставка в хеш-таблицу -- те же O(1). Во-вторых, тебе вставлять-то в таблицу всё равно надо. Я просто объяснял, почему проверял размер, а не делал проверку вхождения элемента в множество. То, что элемент в множество надо вставить - даже не обсуждается. А вот проверить размер - дешевле чем найти вхождение элемента. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 12:46:59 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
MasterZiv Очень юный падаван пишет: > Ну, мы уже выяснили, что на добавление уходит время, зависящее от > количества элементов. Думаю, что время поиска элемента имеет ту же Во-первых, вставка в хеш-таблицу -- те же O(1). Во-вторых, тебе вставлять-то в таблицу всё равно надо. Он делает add + проверку размера, это вдвое дешевле, чем contains + add, если только HashSet не кэширует findPos(), а он его, судя по найденным исходникам, не кэширует. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 12:49:02 |
|
||
|
Как найти число
|
|||
|---|---|---|---|
|
#18+
Код: plaintext 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. Ответы на 1 (поиск нулевых битов) и 3-е задания (поиск дубликатов файлов) у мну тоже есть, могу выложить. Один хрен не взяли ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2009, 13:41:37 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36081732&tid=1344191]: |
0ms |
get settings: |
11ms |
get forum list: |
20ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
207ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
75ms |
get tp. blocked users: |
1ms |
| others: | 198ms |
| total: | 533ms |

| 0 / 0 |
