Приведите все-таки реальные примеры случаев, в которых пользователям будет выгоднее использовать именно ваш сервис. Я сколько вариантов не перебираю — фиксированный объем, пусть и с помесячной оплатой, выходит предпочтительнее, кроме каких-то совсем уж вырожденных случаев.
Банально отказавшись от предложенной вами схемы пересчета места при дедупликации (не отключая её фактически), которая абсолютно непредсказуема и непланируема (откуда я могу знать, что там залито уже на сервисе? А что через месяц будет, если я планирую расходы?), можно сделать возврат места при удалении, что многократно увеличит привлекательность для пользователей.
Ну и опять же, кто целевая аудитория то? Какие юз-кейсы и так далее? Потому что некоторые описанные приемы значительно сужают перспективные аудитории.
Допустим так — Петя загружает файл А в 1 Гб, с него списывается 1$. Я загружаю файл А, с меня списывается 0.5$ за 0.5 Гб, Пете возвращается 0.5$. Затем Петя удаляет файл А, ему возвращаются его оставшиеся 0.5$ (ну или эквивалент в объеме 0.5 Гб). В результате Петя с нейтральным балансом, а я храню полгига бесплатно. Система нагнута.
Или возврата денег за удаление файла не предусмотрено? Если так, то это растет только из поддержки дедупликации, которая может отработать допустим для 10% клиентов, а остальных только отпугнет невозможность возврата денег за удаление файла.
Вы действительно считаете, что пользователи хоть где-то сейчас платят деньги за хранение неуникального контента? Разве что если используют сервис как хранилище для отдачи контента, но это уже совсем другой класс систем.
Ну и вообще, что будет с моим счетом за услуги, если изначально пользователь Петя загрузит файл А, затем я загружу файл А (как я понимаю, он не включится в стоимость), а потом Петя удалит файл А. С меня стоимость хранения этого файла снимут, при том в одностороннем порядке?
Вообще, если уж предполагается упор на долговременное хранение, то часть пользователей захочет использовать этот сервис для хранения бэкапов, где уж точно потребуется частичная дедупликация.
А вообще, подобных файловых хранилищ существует великое множество, и про дедупликацию даже не упоминается, как само собой разумеющееся решение для подобного рода систем. А у вас есть киллерфича или ниша какая-то?
Можно было бы для веселости прикрутить rolling hash и дедуплицировать частично различающиеся файлы (храня оригинал и дельту, конечно). Однако я не могу придумать, кому это нужно, так как контент обычно или совпадает байт-в-байт (фильмы, etc), или полностью различается.
Но если борьба за место серьезная, можно и такое попробовать.
Безусловно, но и углубляться никуда не нужно — эти коэффициенты всего лишь отражают восприятие разных цветов человеком. Оттуда же и растут ноги у цветовых моделей типа YUV.
Но ведь такой сервис не нужен. Яндекс или Google прекрасно решают все проблемы, предлагая альтернативные варианты изображения в других разрешениях и качестве.
Можно посчитать среднее значение градиента для каждой из картинок (применив простейший оператор Собеля, например), где оно больше — то изображение и является первичным. При этом, подсчет можно производить в скользящем окне, заодно и местоположение различающихся областей обнаружить.
Это верно в том случае, если, например, с изображения были искусственно удалены объекты и замещены фоном.
Если преобразовать это же решение (т.е. запоминать «обмены» в отдельном месте, типа хеш-таблицы), то да — O(k) памяти, но время работы будет больше O(k) — необходимо находить индекс элемента в массиве по его новому (после «обмена») индексу.
В цикле, k раз: выбрать рандомный индекс (от 0 до n), вернуть по нему значение из массива, обменять этот элемент с последним, уменьшить n на единицу, повторить. Время — O(k), память — O(1). Профит.
На самом деле, одна из больших проблем связных списков — это пробой кеша, с чем часто можно встречаться, если писать на C++. Для Java это в большинстве случаев не так актуально, т.к. там все равно ссылаемые объекты в другом месте лежат, но если писать что-то высокопроизводительное на примитивных типах, можно серьезно споткнуться об это.
Коммерческие проекты бывают очень и очень разные. Кроме того, относительно структур данных, дело вовсе не ограничивается только производительностью или потреблением памяти.
Иногда для того, чтобы банально все работало так, как ожидается, и не чесать неделю затылок, просто необходимо знать свойства этих структур данных. Например, возможно ли удалять элемент во время итерации по коллекции, какие контракты необходимо соблюдать при работе с ними.
С потокобезопасными коллекциями вообще отдельная песня — их или не используют вообще, тормозя поток на пустом месте блокировкой всего и вся, или используют неправильно, полагаясь на «раз написано Concurrent, значит сам все проблемы с потоками разрулит», и огребая гонки и прочие несогласованности.
А что за компания, если не секрет? Мне кажется, не так уж и много в нашей стране компаний, требующих от соискателей умения отвечать на обозначенные выше вопросы.
Отчего же, согласен, но дело ведь в том, что подобного от этих 90% и не требуется — для решаемых ими проблем в подобных знаниях и умениях необходимости нет.
Но если уж вопрос заходит о том, что от соискателя требуются хотя бы знания базовых алгоритмов, структур данных, минимальные навыки проектирования, да и просто голова на плечах — стоит придумать более сложные и разносторонние задачи.
Ну и опять же, кто целевая аудитория то? Какие юз-кейсы и так далее? Потому что некоторые описанные приемы значительно сужают перспективные аудитории.
Или возврата денег за удаление файла не предусмотрено? Если так, то это растет только из поддержки дедупликации, которая может отработать допустим для 10% клиентов, а остальных только отпугнет невозможность возврата денег за удаление файла.
Ну и вообще, что будет с моим счетом за услуги, если изначально пользователь Петя загрузит файл А, затем я загружу файл А (как я понимаю, он не включится в стоимость), а потом Петя удалит файл А. С меня стоимость хранения этого файла снимут, при том в одностороннем порядке?
А вообще, подобных файловых хранилищ существует великое множество, и про дедупликацию даже не упоминается, как само собой разумеющееся решение для подобного рода систем. А у вас есть киллерфича или ниша какая-то?
Но если борьба за место серьезная, можно и такое попробовать.
Это верно в том случае, если, например, с изображения были искусственно удалены объекты и замещены фоном.
Иногда для того, чтобы банально все работало так, как ожидается, и не чесать неделю затылок, просто необходимо знать свойства этих структур данных. Например, возможно ли удалять элемент во время итерации по коллекции, какие контракты необходимо соблюдать при работе с ними.
С потокобезопасными коллекциями вообще отдельная песня — их или не используют вообще, тормозя поток на пустом месте блокировкой всего и вся, или используют неправильно, полагаясь на «раз написано Concurrent, значит сам все проблемы с потоками разрулит», и огребая гонки и прочие несогласованности.
И что ж это за компания такая, в которой вы работаете, что люди готовы на собеседованиях по 3-4 часа сидеть и писать что-то?
Но если уж вопрос заходит о том, что от соискателя требуются хотя бы знания базовых алгоритмов, структур данных, минимальные навыки проектирования, да и просто голова на плечах — стоит придумать более сложные и разносторонние задачи.