Имеется большой массив значений времени с обнулёнными секундами (например, "14:23:00"). Среди этих значений могут встречаться повторения. Необходимо сделать так, чтобы все значения были уникальными, изменив секунды (они не несут информации). Это можно сделать, например, случайным образом добавляя секунды, но существует, хоть и малая, вероятность, что одинаковым значениеям будет добавлено одинаковое количество секунд. Как этого избежать? Возможно есть другие способы сделать значения уникальными?

Здравствуйте, anonymous, Вы писали:

A>Имеется большой массив значений времени с обнулёнными секундами (например, "14:23:00"). Среди этих значений могут встречаться повторения. Необходимо сделать так, чтобы все значения были уникальными, изменив секунды (они не несут информации). Это можно сделать, например, случайным образом добавляя секунды, но существует, хоть и малая, вероятность, что одинаковым значениеям будет добавлено одинаковое количество секунд. Как этого избежать? Возможно есть другие способы сделать значения уникальными?

Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.

Здравствуйте, _DAle_, Вы писали:

_DA>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.

Ужас какой. Достаточно использовать один циклический счётчик с = ( с + 1 ) % 60, и отсортированную по времени исходную последовательность.

Здравствуйте, <Аноним>, Вы писали:

А>Здравствуйте, _DAle_, Вы писали:

_DA>>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.

А>Ужас какой. Достаточно использовать один циклический счётчик с = ( с + 1 ) % 60, и отсортированную по времени исходную последовательность.

Так для этого отсортировать последовательность надо. А нигде не говорилось в исходном посте, что нам не важен порядок. Так что не надо ужасаться.

Здравствуйте, _DAle_, Вы писали:

_DA>Так для этого отсортировать последовательность надо. А нигде не говорилось в исходном посте, что нам не важен порядок. Так что не надо ужасаться.

Ладна, считай что отмазалси.

Здравствуйте, _DAle_, Вы писали:

_DA>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.

Слишком накладно, особенно если кроме времени будут ещё и даты.

Здравствуйте, Аноним, Вы писали:

_DA>>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.
А>Ужас какой. Достаточно использовать один циклический счётчик с = ( с + 1 ) % 60, и отсортированную по времени исходную последовательность.

Сортировки хотелось бы избежать.

Здравствуйте, anonymous, Вы писали:

A>Здравствуйте, _DAle_, Вы писали:

_DA>>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.

A>Слишком накладно, особенно если кроме времени будут ещё и даты.

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

Здравствуйте, anonymous, Вы писали:

А>>Ужас какой. Достаточно использовать один циклический счётчик с = ( с + 1 ) % 60, и отсортированную по времени исходную последовательность.

A>Сортировки хотелось бы избежать.

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

Здравствуйте, Аноним, Вы писали:

А>>>Ужас какой. Достаточно использовать один циклический счётчик с = ( с + 1 ) % 60, и отсортированную по времени исходную последовательность.
A>>Сортировки хотелось бы избежать.
А>Если знать мин. и макс. возможные даты и количество дат, то можно оценить, какой из двух вариантов будет быстрее.

Зараннее минимальная и максимальная даты не известны, чтобы их найти придётся перебирать их все, а тогда уж лучше отсортировать. Количество их может быть в от 6000 до 11000, по крайней мере пока так было.

Здравствуйте, _DAle_, Вы писали:

_DA>>>Добавлять секунды не случайным образом, для этого для каждого времени (часы/минуты) надо хранить счетчик. Заводится массив, содержащий 24*60 элементов, изначально обнуленный. Затем проходим по исходному массиву, добавляем соответствующее количество секунд и увеличиваем соответствующий счетчик.
A>>Слишком накладно, особенно если кроме времени будут ещё и даты.
_DA>Ок, тогда надо четче поставить задачу. На каком множестве заданы данные, есть ли какие-нибудь ограничения на их количество, какие ограничения по памяти, и вообще какие требования к алгоритму.

Уточняю. ) Все эти даты — результат разбора текстового файла, соответственно поступают они по одной, и изначально не известны они все и их количество. Хотя практика показывает, что обычно их количество лежит в диапазоне от 6000 до 11000. Множество не ограничено, хотя большинство дат в диапазоне месяца. После извлечения даты созраняются в виртуальную таблицу. Так вот хотелось бы узнать, можно ли их изменить сразу после извлечения или придётся потом работать с виртуальной таблицей заполненной данными?

Здравствуйте, anonymous, Вы писали:

A>Множество не ограничено, хотя большинство дат в диапазоне месяца. После извлечения даты созраняются в виртуальную таблицу.

Можешь сделать таблицу счётчиков 30*24*60 (~40K памяти) Что в диапазон не попадает — пихать в map счётчиков.

Здравствуйте, anonymous, Вы писали:

A>Уточняю. ) Все эти даты — результат разбора текстового файла, соответственно поступают они по одной, и изначально не известны они все и их количество. Хотя практика показывает, что обычно их количество лежит в диапазоне от 6000 до 11000. Множество не ограничено, хотя большинство дат в диапазоне месяца. После извлечения даты созраняются в виртуальную таблицу. Так вот хотелось бы узнать, можно ли их изменить сразу после извлечения или придётся потом работать с виртуальной таблицей заполненной данными?

Добавлять секунды сразу при разборе с использованием константной памяти не получится. Если важно добавлять секунды он-лайн, то можно использовать хеш-таблицу, отображающую дату в счетчик, и увеличивать счетчик при обнаружении даты в таблице. Если дополнительную память совсем не хочется использовать, то можно воспользоваться методом, предложенным выше, с сортировкой и одним счетчиком.

А что ты будешь делать если какое-либо время встретится больше 60 раз ? обеспечить уникальность только приписыванием секунд не выйдет.

Здравствуйте, Аноним, Вы писали:

А>А что ты будешь делать если какое-либо время встретится больше 60 раз ? обеспечить уникальность только приписыванием секунд не выйдет.

В моём случае это не возможно, предположительно количество совпадающих значений может быть не больше 4, хотя я пока встречал только по 2 совпадающих значения.

Здравствуйте, anonymous, Вы писали:

A>Имеется большой массив значений времени с обнулёнными секундами (например, "14:23:00"). Среди этих значений могут встречаться повторения. Необходимо сделать так, чтобы все значения были уникальными, изменив секунды (они не несут информации). Это можно сделать, например, случайным образом добавляя секунды, но существует, хоть и малая, вероятность, что одинаковым значениеям будет добавлено одинаковое количество секунд. Как этого избежать? Возможно есть другие способы сделать значения уникальными?

а что делать, если подряд будут идти шестьдесят одна штука "14:23:00" ?

Здравствуйте, Аноним, Вы писали:

А>Ладна, считай что отмазалси.
Еще вспомни какая сложность у сортировки и пойми, что твой алгоритм хоть на словах и звучит проще, в реальности вместо сложности O(N) предлагает в лучшем случае, если я правильно помню, O(N*log(N)).

Здравствуйте, Рома Мик, Вы писали:

РМ>Еще вспомни какая сложность у сортировки и пойми, что твой алгоритм хоть на словах и звучит проще, в реальности вместо сложности O(N) предлагает в лучшем случае, если я правильно помню, O(N*log(N)).

Молодец, помнишь правильно. Тока чтоб получить данные в нужном порядке далеко не всегда нужно что-то сортировать. Иногда к тексту программы достаточно добавить три слова "ORDER BY 1"

Здравствуйте, Megabyte, Вы писали:

A>>Имеется большой массив значений времени с обнулёнными секундами (например, "14:23:00"). Среди этих значений могут встречаться повторения. Необходимо сделать так, чтобы все значения были уникальными, изменив секунды (они не несут информации). Это можно сделать, например, случайным образом добавляя секунды, но существует, хоть и малая, вероятность, что одинаковым значениеям будет добавлено одинаковое количество секунд. Как этого избежать? Возможно есть другие способы сделать значения уникальными?
M>а что делать, если подряд будут идти шестьдесят одна штука "14:23:00" ?

Такого не будет по физическим причинам. Эти значения показывают время телефонных звонков, а сколько раз за минуту можно позвонить с одного номера? Далеко не 60.

A>Имеется большой массив значений времени с обнулёнными секундами (например, "14:23:00"). Среди этих значений могут встречаться повторения. Необходимо сделать так, чтобы все значения были уникальными, изменив секунды (они не несут информации). Это можно сделать, например, случайным образом добавляя секунды, но существует, хоть и малая, вероятность, что одинаковым значениеям будет добавлено одинаковое количество секунд. Как этого избежать? Возможно есть другие способы сделать значения уникальными?

Неразрешима. Если значение "14:23:00" встретится 61 раз — то никакие секунды уже не помогут.