Очень интересно мнение сообщества по этому вопросу. Заранее благодарен за ваши комментарии.
Ок:) Представим, что помимо срочных писем бывают еще предоплаченные, заказные и с уведомлением. А теперь представим что письмо может быть и срочным и заказным одновременно. В этом случае при использовании наследования возникает классическая ловушка, когда необходимый функционал размещен в другом независимом классе.
В рассматриваемой задаче видится более естественным использовать аттрибуты — некие дополнительные маркеры, содержащиеся в письме, описывающие его доп. свойста.
В наивной реализации можно было бы сделать так:
[Flags]
public enum PostAttrFlags
{
Urgent,
Prepaid,
//...
}
public interface IParcelSimple
{
string Barcode { get; set; }
PostAttrFlags Attributes { get; }
}
public class ParcelSimple : IParcelSimple
{
public string Barcode { get; set; }
public PostAttrFlags Attributes { get; }
}
В более углубленной, выделим аттрибут в отдельный интерфейс, где письмо содержит множество (HashSet) таких элементов:
public interface IParcelAttribute
{
}
public struct ParcelAttrPrepaid : IParcelAttribute
{
}
public struct ParcelAttrUrgent : IParcelAttribute
{
}
public interface IParcel
{
string Barcode { get; set; }
HashSet<IParcelAttribute> Attributes { get; }
}
public class Parcel : IParcel
{
public string Barcode { get; set; } = "";
public HashSet<IParcelAttribute> Attributes { get; set; } = new HashSet<IParcelAttribute>();
}
Вторая реализация дает интересные следствия:
Аттрибут может быть обычной пометкой. Для этого достаточно обозваться IParcelAttribute
Часть бизнес логики реализуется с помощью возможностей строгой типизации и фундаментальных алгоритмов (HashSet гарантирует уникальность аттрибутов и быстрый доступ к конкретному аттрибуту письма, контроль типов гарантирует получение полных сведений о письме на всем протяжении отправки) и т.д.
Выделение аттрибутов как отдельной сущности, позволяет проделывать с письмами интересные штуки. Например, «Сортировочный центр» может поставить отметку на письмо что оно прибыло на сортировку тогда-то и тогда-то, покинуло сортировку тогда-то и тогда-то и т.д.
Теситровать такой код легче
Кстати, потестим наш код, что бы убедится в сказанном:
namespace UnitPost
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void TestIsParcel()
{
//-- Создадим срочную посылку
Parcel p = new Parcel();
p.Attributes.Add(new ParcelAttrUrgent());
//-- Убедимся что это именно срочная посылка
Assert.AreEqual(p.Attributes.Where(t => t.GetType() == typeof(ParcelAttrUrgent)).Any(), true);
}
[TestMethod]
public void TestDblUrgentExcept()
{
//-- Создадим срочную посылку
Parcel p = new Parcel();
p.Attributes.Add(new ParcelAttrUrgent());
//-- Дважды срочную посылку создать не получится
Assert.AreEqual(p.Attributes.Add(new ParcelAttrUrgent()), false);
}
}
}
Репитеры как правило и так работают только с одним бандом. Есть и мультидиапазонные, но они стоят в разы дороже.
Мощность ретранслированного сигнала у репитеров и так ничтожна. Достаточно отойти от него на несколько метров, что бы сигнал исчез. Именно поэтому достаточно вынести принимающую антенну от ретранслирующей, всего на 5-6 метров и самовозбуждения уже не будет.
Репитеры не нужны в городах. С покрытием там и так все впорядке. Если сигнал не пробивает толстую стену, для этого есть более простые решения: например просто вывести принимающую антенну наружу.
На алиэкспресс мне не попадались репитеры. Скорее это просто "улучшители связи". Об этом там прямо предупреждают продавцы: "устройство служит для улучшения существующего сигнала связи" - если сигнала нет, китайский "репитер" не поможет.
В условиях когда вышка БС удалена и, что еще хуже, находится в не зоны Френеля (например за горой как в моем случае), несуществует иного способа установить связь, чем использовать ретранслятор. Направленные антенны требуют хорошей "видимости" БС, всенаправленные слабы. Рельеф местности делает невозможным использовать мачты (в моем случае например мне понадобилась бы мачта 60 метров и выше).
Ретрансляторы эффективны в диких местах, на пересеченной местности. Когда нет вообще никаких сигналов, включая помех и наводок. Девственно чистый эфир:)
У операторов и так есть возможность банить польователей, без привлечения минкомцифры. Меня например забанили в МТС довольно быстро с моим репитером, хотя я точно никому не мог помешать, так как соседий нет в радиусе нескольких км.
Если ты, как оператор предлагаешь отстойное покрытие, а твои пользователи бегут от тебя как с тонущего коробля, - то да, нужно жаловатся в минцифры и обвинять маленькие черные коробочки мощностью несколько ватт, - это они виноваты во всех твоих бедах. Не ты, не твои маркетологи-шоумены - а пользователи.
Помню писал свою версию сравнения чисел double, основанную на целочисленном сравнении. Каково же было моё удивление, когда бенчмарк показал равные результаты, с незначительным опережением стандартного сравнения double. После этого я понял, что написать быстрее чем это реализовано в промышленной реализации крайне непросто. Вы повторяет как мантру слово "оптимизация" хотя в задании не было явного утверждения о оптимизации любой ценой и доведения её до максимально возможной. Вы же зациклились на этом предложении возведя его в обсолют, в основном правда из-за бестолковой формулировки самого задания. Отсюда имхо, все и пошло не поплану.
Да, согласен, описание такое себе. Что же, выложил на github эту версию алгоритма. Поиск за O(n) без всяких множетелей. Потребление памяти можно довести практически до константных значений. Это не продакшен версия, но ее можно доработать, что бы она работала в динамике.
Уже многие отметились. Попробую предложить что-то новое. Ищем за один проход. Перебираем поэлементно. Каждый элемент i образует либо новую цепочку LinkedList, либо присоединяется к существующей. Если есть цепочка с последним элементом равным i-1, то элемент присоединяется к ней в конец (становится ее последним элементом), если есть цепочка c первым элементом i+1 то в начало (становится ее первым элементом). Если нет ни одной такой подходящей цепочки — создается новая.
В третьем примере множества a={11, 10, 9, 8,15,14,13,12,3,2...106,104} последовательно перибирая элементы, дойдя до a[3] будем иметь одну цепочку от 8 до 11, на a[4] будет уже две цепочки {8:11}, {15}, a[7] — две цепочки {8:11}, {12:15} и т.д.
Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.
После перебора всех элементов массива, будет образован набор цепочек. В любом случае первый отсутствующий элемент будет определен как либо:
а) n-1, где n первый элемент цепочки, при n-1 != 0,
б) либо k+1, где k — последний элемент первой цепочки.
Объяснение получилось громоздким, но думаю плюсы у данного алго найдутся: не требуется сортировка. Можно сделать за один проход. По памяти не требователен (сумма длин всех цепочек равна количеству элементов, правда нужна доп. память на быстрый поиск по корням и вершинам). Должен любить работать с множествами, где отсутствующих элементов почти нет.
Да, постраюсь предоставить решение. Уж не знаю как его лучше будет оформить, возможно даже в виде небольшой статьи-довеска.
Что касается проблематики вопроса, то вспомнилась весьма неплохая книга Роберта Седжвика «Алгоритмы на Java», конкретно, ее раздел посвященный разряженным векторам, в русском 4-ом издании 453 страница. Впрочем там весьма мутно и поверхностно все это описывается, но оно и понятно, потому что тема довольно сложная. Однако, в нашем случае с тегами, думаю все можно упростить.
При всем уважении к предложенному Вами алгоритму, все же замечу (имхо) что решение через разряженные матрицы было бы более изящным и главное универсальным. Я посидел с листком бумаги над Вашей задачей — и действительно, прослеживается довольно интересный алгоритм с очень эффективным рассчетом и кординальным снежением размерности пространства поиска решения.
Ок:) Представим, что помимо срочных писем бывают еще предоплаченные, заказные и с уведомлением. А теперь представим что письмо может быть и срочным и заказным одновременно. В этом случае при использовании наследования возникает классическая ловушка, когда необходимый функционал размещен в другом независимом классе.
В рассматриваемой задаче видится более естественным использовать аттрибуты — некие дополнительные маркеры, содержащиеся в письме, описывающие его доп. свойста.
В наивной реализации можно было бы сделать так:
В более углубленной, выделим аттрибут в отдельный интерфейс, где письмо содержит множество (HashSet) таких элементов:
Вторая реализация дает интересные следствия:
Кстати, потестим наш код, что бы убедится в сказанном:
Да, действительно работает.
Репитеры как правило и так работают только с одним бандом. Есть и мультидиапазонные, но они стоят в разы дороже.
Мощность ретранслированного сигнала у репитеров и так ничтожна. Достаточно отойти от него на несколько метров, что бы сигнал исчез. Именно поэтому достаточно вынести принимающую антенну от ретранслирующей, всего на 5-6 метров и самовозбуждения уже не будет.
Репитеры не нужны в городах. С покрытием там и так все впорядке. Если сигнал не пробивает толстую стену, для этого есть более простые решения: например просто вывести принимающую антенну наружу.
На алиэкспресс мне не попадались репитеры. Скорее это просто "улучшители связи". Об этом там прямо предупреждают продавцы: "устройство служит для улучшения существующего сигнала связи" - если сигнала нет, китайский "репитер" не поможет.
В условиях когда вышка БС удалена и, что еще хуже, находится в не зоны Френеля (например за горой как в моем случае), несуществует иного способа установить связь, чем использовать ретранслятор. Направленные антенны требуют хорошей "видимости" БС, всенаправленные слабы. Рельеф местности делает невозможным использовать мачты (в моем случае например мне понадобилась бы мачта 60 метров и выше).
Ретрансляторы эффективны в диких местах, на пересеченной местности. Когда нет вообще никаких сигналов, включая помех и наводок. Девственно чистый эфир:)
У операторов и так есть возможность банить польователей, без привлечения минкомцифры. Меня например забанили в МТС довольно быстро с моим репитером, хотя я точно никому не мог помешать, так как соседий нет в радиусе нескольких км.
Если ты, как оператор предлагаешь отстойное покрытие, а твои пользователи бегут от тебя как с тонущего коробля, - то да, нужно жаловатся в минцифры и обвинять маленькие черные коробочки мощностью несколько ватт, - это они виноваты во всех твоих бедах. Не ты, не твои маркетологи-шоумены - а пользователи.
Помню писал свою версию сравнения чисел double, основанную на целочисленном сравнении. Каково же было моё удивление, когда бенчмарк показал равные результаты, с незначительным опережением стандартного сравнения double. После этого я понял, что написать быстрее чем это реализовано в промышленной реализации крайне непросто. Вы повторяет как мантру слово "оптимизация" хотя в задании не было явного утверждения о оптимизации любой ценой и доведения её до максимально возможной. Вы же зациклились на этом предложении возведя его в обсолют, в основном правда из-за бестолковой формулировки самого задания. Отсюда имхо, все и пошло не поплану.
Да, согласен, описание такое себе. Что же, выложил на github эту версию алгоритма. Поиск за O(n) без всяких множетелей. Потребление памяти можно довести практически до константных значений. Это не продакшен версия, но ее можно доработать, что бы она работала в динамике.
Уже многие отметились. Попробую предложить что-то новое. Ищем за один проход. Перебираем поэлементно. Каждый элемент i образует либо новую цепочку LinkedList, либо присоединяется к существующей. Если есть цепочка с последним элементом равным i-1, то элемент присоединяется к ней в конец (становится ее последним элементом), если есть цепочка c первым элементом i+1 то в начало (становится ее первым элементом). Если нет ни одной такой подходящей цепочки — создается новая.
В третьем примере множества a={11, 10, 9, 8,15,14,13,12,3,2...106,104} последовательно перибирая элементы, дойдя до a[3] будем иметь одну цепочку от 8 до 11, на a[4] будет уже две цепочки {8:11}, {15}, a[7] — две цепочки {8:11}, {12:15} и т.д.
Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.
После перебора всех элементов массива, будет образован набор цепочек. В любом случае первый отсутствующий элемент будет определен как либо:
а) n-1, где n первый элемент цепочки, при n-1 != 0,
б) либо k+1, где k — последний элемент первой цепочки.
Объяснение получилось громоздким, но думаю плюсы у данного алго найдутся: не требуется сортировка. Можно сделать за один проход. По памяти не требователен (сумма длин всех цепочек равна количеству элементов, правда нужна доп. память на быстрый поиск по корням и вершинам). Должен любить работать с множествами, где отсутствующих элементов почти нет.
Что касается проблематики вопроса, то вспомнилась весьма неплохая книга Роберта Седжвика «Алгоритмы на Java», конкретно, ее раздел посвященный разряженным векторам, в русском 4-ом издании 453 страница. Впрочем там весьма мутно и поверхностно все это описывается, но оно и понятно, потому что тема довольно сложная. Однако, в нашем случае с тегами, думаю все можно упростить.