Java - правильная реализация алгоритмов сортировки - PullRequest
Новая
       32

Java - правильная реализация алгоритмов сортировки

2 голосов
/ 20 июля 2010

В настоящее время я играю с реализацией различных алгоритмов сортировки в Java, в основном для развлечения, но я борюсь с тем, как сделать это «правильно». То есть я хочу, чтобы пользователь мог вызывать алгоритм сортировки по своему выбору для всего, что сопоставимо - int s, long s, String s, boolean s (фактически, они сопоставимы в Java ?) свои занятия; без разницы. Вопрос в том, как это сделать.

Я думал об использовании класса для представления алгоритма сортировки и, следовательно, для хранения вещей, которые должны быть отсортированы внутри, с использованием общего списка или чего-либо еще (List<E>). Это также позволило бы мне использовать несколько конструкторов и, таким образом, позволить пользователю передавать данные в различных формах - списки, массивы, что угодно. Это правильный способ сделать это? Моя текущая проблема заключается в том, что я не хочу, чтобы пользователь создавал класс, когда он хочет что-то отсортировать, я бы предпочел, чтобы его можно было назвать очень похожим на System.out.println или тому подобное. 

// Example:

int[] myInts = {5,4,3,2,1};

// This is what I do *not* want.
InsertionSort mySort = new InsertionSort();
int[] sortedInts = mySort.sort(myInts);

// This is more like what I want.
int[] sortedInts = Sorting.insertionSort(myInts);

Я прошу прощения за то, что может показаться базовым вопросом, но я только изучаю свой язык программирования. Это немного нелепо для студента 2 nd года, работающего в софтверной компании на летней работе, но вы будете удивлены, насколько мало знаний по программированию требуется для большинства моя работа ... это обычно больше знаний о дизайне.

EDIT:

Для ясности, у меня есть три основных вопроса:

  • Лучше ли, чтобы пользователь создал класс для сортировки, или чтобы статический метод был в классе, который импортирует пользователь?
  • Можно ли легко иметь дело как с примитивными типами данных, так и с универсальными объектами? Так как я хочу иметь возможность обрабатывать любой универсальный объект, который реализует сравнимый (или аналогично), это вызывает проблемы с примитивами (так как они ничего не реализуют;)).
  • Каков наилучший способ обработки общего ввода - что я должен проверить, прежде чем пытаться отсортировать их (например, реализовать Comparable)?

Ответы [ 4 ]

1 голос
/ 20 июля 2010

Нормальным способом реализации алгоритма сортировки является реализация статического метода, например, взгляните на исходный код Arrays.sort ().Вы можете перегружать этот метод различными реализациями для разных типов параметров (например, объекты, которые реализуют сопоставимые и предоставляют свой собственный компаратор по сравнению с примитивными массивами и т. Д.)1005 * Однако я могу представить две веские причины для реализации алгоритма сортировки как класса, в котором вы генерируете свой собственный экземпляр:

  • Это позволяет вам полиморфно передавать экземпляры алгоритмов сортировки - это может быть полезнонапример, если вы создавали коллекцию алгоритмов сортировки и хотели запустить, например, множество тестов для них.
  • У вас может быть закрытое состояние в экземпляре сортировщика - это полезно для некоторых алгоритмов сортировки, например, для некоторых-распределенные массивы для временного хранения, и имеет смысл поместить его в экземпляр класса, если вы хотите иметь возможность одновременно использовать разные экземпляры сортировки из нескольких потоков - для реализации статического метода потребуется некоторая форма синхронизации (например, см. использованиеTон ThreadLocal в коде выше).
1 голос
/ 20 июля 2010

Я думаю, что вы ответили на свой вопрос? Если вы хотите предоставить статический метод вместо того, чтобы заставлять пользователя создавать, возражать и вызывать метод экземпляра, просто сделайте это. Sorting.insertionSort() выглядит хорошо для меня.

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

1 голос
/ 20 июля 2010

Вы можете взять в качестве примера способ <a href="http://download.oracle.com/docs/cd/E17409_01/javase/6/docs/api/java/util/Collections.html" rel="nofollow noreferrer">Collections</a>, обеспечивающий операцию binarySearch ... И действительно, 

int[] sortedInts = Sorting.insertionSort(myInts);

более Java-способ, даже если бы я лично предпочел 

public class Sorting {
     public static <DataType extends Comparable> Iterable<DataType> insertionSort(Iterable<DataType> data);
}
  • <DataType> убедитесь, что выходные данные имеют тот же тип, что и входные
  • Iterable<DataType> входные данные являются итеративными, чтобы обеспечить максимальную совместимость.Очевидно, что использование List было бы намного проще, поскольку оно позволяет переупорядочивать внутренние элементы.Однако, используя итеративную гарантию, разработчик этого метода должен будет заново создать список, чтобы изменить его, гарантируя, что входной список останется неизменным и что выходной список будет другим.

Поскольку я только что видел, как вы редактируете свой вопрос, позвольте мне ответить на него по пунктам (и подумайте над выбором ответа после этого, поскольку легче добавлять новые вопросы, чем бесконечно редактировать существующие - если вы не зададите свой вопросвики сообщества, как я делаю из этого ответа)

Лучше ли пользователю создать класс для сортировки или иметь статический метод в классе, который импортирует пользователь?

На мой взгляд, использование статического метода в этом случае предпочтительнее, поскольку здесь вам приходится манипулировать объектами, которые вы не создавали, довольно «базовым» способом.

Можно ли легко иметь дело как с примитивными типами данных, так и с универсальными объектами? Поскольку я хочу иметь возможность обрабатывать любой универсальный объект, который реализует Comparable (или аналогично), tЗатем он вызывает проблемы с примитивами (поскольку они ничего не реализуют;)).

Вы слышали о autoboxing ?Это особенность Java 5, которая делает первичные типы «эквивалентами» объектов.То есть int автоматически преобразуются в Integer, который, как вы знаете, реализует Comparable.

Каков наилучший способ обработки общего ввода - что я должен проверить, прежде чем пытаться отсортировать их (например, реализует Comparable)?

Обратите внимание, что из-за объявления моего метода (the) проверка того, что входные данные реализуют Comparable, выполняется не вами, а компилятором Jav, что позволяет вашей IDEпокажу вам ошибки.

0 голосов
/ 20 июля 2010

Я не уверен, что это то, с чем вы боретесь ... но практически невозможно реализовать алгоритм, который работает как для ссылочных типов, так и (реальных) примитивных типов. Причина в том, что система типов Java не имеет условного универсального типа, который имеет примитивные типы и Object в качестве подтипов.

Обычный обходной путь для этого - обернуть примитивные типы, используя их соответствующие классы-обертки; например Integer для int, Boolean для bool и так далее. Это позволяет реализовать (например) алгоритмы сортировки, которые для любого Collection<T> или любого <T>[].

Этот подход имеет проблемы с производительностью / использованием памяти применительно к большим массивам (скажем) целых чисел. Либо вы носите снижение производительности, либо реализуете алгоритм и поддерживающие его классы отдельно для каждого примитивного типа.

(я сказал рядом с невозможно, потому что можно абстрагировать сравнение пары элементов массива и обмен пары элементов массива таким образом, чтобы не раскрывать фактический тип элемента в интерфейсе, например 

public interface ArraySortAdapter {
  public abstract int compareElements(Object array, int pos1, int pos2);
  public abstract void swapElements(Object array, int pos1, int pos2);
}

и предоставляют разные реализации для разных типов массивов; например, 

public class IntArraySortAdapter implements ArraySortAdapter {
  public int compareElements(Object array, int pos1, int pos2) {
      int[] intArray = (int[]) array;
      if (intArray[pos1] < intArray[pos2]) {
          return -1;
      } else if (intArray[pos1] > intArray[pos2]) {
          return +1;
      } else {
          return 0;
      }
  }

  ...
}

Однако это громоздко и неэффективно, если не сказать больше ...)

...