Эффективные способы отсортировать деку фактических карт
Ответ Antamir был очень полезен для меня, но у него есть ошибка в том, что он не подтверждает, что количество параметров в найденном методе соответствует количеству типов, переданных при составлении сочетания общих и конкретных типов.
Например, если вы запустили:
type.GetMethod("MyMethod",typeof(Refl.T1),typeof(bool))
, он не может различать два метода:
MyMethod<T>(T arg1)
MyMethod<T>(T arg1, bool arg2)
Два вызова:
var p = method.GetParameters();
следует изменить на:
var p = method.GetParameters();
if (p.Length != parameters.Length)
{
correct = false;
continue;
}
Кроме того, обе существующие строки «break» должны быть «продолжены».
4 ответа
Я думаю, что быстрая сортировка - самый простой способ для этого. Кажется, на Youtube даже было несколько видео, показывающих, как люди делают это с обычной покерной колодой.
Вы перебираете колоду и кладете все карты меньше 100 в левую кучу, все большие - в правую. Затем вы перебираете все кучи, сначала глубину (чтобы не было слишком много куч сразу). На определенном пороге (возможно, около 5 карт) вы просто сортируете "в руке" (аналогично сортировке вставкой, возможно). Наконец, вы складываете кучи вместе.
Вы также можете сделать сортировку слиянием: Разделите кучу на две, сначала пересматривайте глубину, пока не получите две кучи по 5 карт в каждой. Отсортируйте эти две кучи "в руке", затем положите их лицом вверх рядом друг с другом. Объедините их в итоговую кучу, всегда кладя нижнюю из показанных карт в итоговую кучу. Вы можете видеть, какие стопки уже отсортированы, оставляя их лицевой стороной вверх. Следите за тем, чтобы всегда объединять кучи одинакового размера, иначе переходите к разделению следующей несортированной кучи.
Редактирование: радиксная сортировка тоже может подойти: Разложите карты в десять кучек по последней цифре, сложите эти кучки по порядку. Затем разложите карточки в десять кучек по предпоследней цифре, снова сложите их по порядку. Наконец, разложите их в стопки по предпоследней цифре (согласно вашему описанию, это первая цифра) и сложите их вместе, готово. Это может быть самым простым, в конце концов, и это O(n) (вам нужно три прохода через колоду).
Я преподавал в университетских классах, которые иногда занимают большую часть, и у меня была практика с аналогичной задачей сортировки экзаменов. Я почти всегда использую сортировку ведрами, как и вы. Вы также упоминаете подход сортировки слиянием, который я иногда использую, но он экономит время только тогда, когда вы начинаете с отсортированных подгрупп, а не с полностью зашифрованным набором карт.
Существуют приемы для ускорения сортировки ведра. Большую часть времени в сортировке людей ведро тратится на подсчет ведра для следующего предмета. Вы можете попробовать два трюка. Во-первых, вы можете сортировать сегменты по цифрам, которые, я полагаю, называются сортировкой по основанию, так что вам никогда не придется сравнивать числа. На первом этапе используются три ведра, что не очень много, но может быть хорошо. Второй этап - «основная» работа с десятью ведрами. На третьем этапе вы сортируете десять пронумерованных карточек, и здравый смысл подсказывает сортировку вставок. Но даже на этом этапе радикальная сортировка может ускорить процесс, даже если каждая корзина получает только одну карту. Конечно, вы не должны использовать «ведра» с четырьмя сторонами, а только груды карт на столе. Вы можете использовать метод «ведро» для цифры единиц только в том случае, если карты легко подметать по порядку. Возможно для средней стадии, слот с тремя сторонами будет работать лучше, чем открытая колода карт.
Второй трюк - пометить места на столе от 0 до 9, чтобы вы могли быстрее найти нужную кучу. Этикетки можно наклеивать на стол, чтобы их можно было использовать повторно.
Я не уверен, что именно эта стратегия сортировки ведра является лучшей. Дело в том, что сортировка по группам является наиболее распространенным методом сортировки промежуточных слов и, вероятно, лучше всего подходит для больших колод карт. Есть несколько вариантов, и вам нужно немного поэкспериментировать, чтобы увидеть, какой из них работает лучше всего.
Причина, по которой я спрашиваю о фактических общих числах и размерах, заключается в том, что если общая площадь всех возможных карт достаточно мала, то вполне возможно просто: пройтись по колоде, раскладывая их все в сетку, каждая карта ложится на свое место, а затем просто подбирать их по порядку.
Например, если бы было максимум 100 карт, пронумерованных 1-100, представьте, что ваша рабочая поверхность разделена на прямоугольную сетку 10 x 10; тогда по мере обработки каждой карты кладите карту 67 в 7-й столбец 6-го ряда. Когда все карточки разложены, поднимите их по порядку.
Это работает, только если ваша рабочая поверхность достаточно велика, чтобы вместить все карты, но если они обычного размера и у вас есть большой стол, он должен справиться с 200, о которых вы упомянули, тем более что вы можете легко перекрывать "ячейки", и метод все равно будет работать.
Для меня это подход, который в наибольшей степени использует тот факт, что это проблема в физическом пространстве, а не в битах - каждый физический объект обрабатывается только дважды (один раз, чтобы поставить его на место, другой - чтобы поднять), потому что для алгоритма, включающего физические объекты, перемещение их вокруг имеет гораздо большую стоимость, чем обдумывание того, что делать.
Я думаю, что счетная сортировка вместе с вашим подходом к сортировке вставками может хорошо работать: сканируйте на единицы и помещайте их первыми, затем двойки и так далее.
Это может показаться большой работой, поскольку ваши карточки пронумерованы от 1 до более чем 200, но я думаю, что в этом случае все будет большой работой. Вы можете ускорить процесс, если будете работать с несколькими картами одновременно, что не должно быть слишком сложно: просканируйте все карты одновременно на наличие единиц, двоек и троек (и больше, если вы готовы к этому) и поместите их в соответствующие позиции (комбинируя с "сортировкой вставкой", чтобы не оставлять пустое пространство между картами).