Индивидуальный заказ на Java для Сортировка

Question

Каков наилучший (с точки зрения эффективности времени и пространства) способ реализации Java-компаратора для сортировки коллекций с использованием пользовательского заказа. Например - я хочу, чтобы отсортировать массив, используя следующий порядок -

RWQOJMVAHBSGZXNTCIEKUPDYFL

У меня есть следующий код Java, который работает, как ожидалось, но не уверен, если есть какой-либо другой эффективный способ сделать то же самое.

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 
import java.util.List; 
import java.lang.Math; 

public class DiffSort { 

    private static String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL"; 

    // sort with comparator 
    public static Comparator<String> diffNaturalOrder = new Comparator<String>() { 
     public int compare(String v, String w) { 
      int diff = 0, iter = 0; 
      Integer index1, index2; 
      Integer len1 = v.length(); 
      Integer len2 = w.length(); 
      int len = Math.min(len1, len2); // lesser of 2 strings 

      for(int i=0; i<len; i++) { 
       index1 = order.indexOf(v.charAt(i)); 
       index2 = order.indexOf(w.charAt(i)); 
       // if both chars are absent in order string, use natural ordering 
       if(index1 == -1 && index2 == -1) 
        diff = new Character(v.charAt(i)).compareTo(new Character(w.charAt(i))); 
       else if(index1 == -1 && index2 > 0) 
        diff = 1; 
       else if(index1 > 0 && index2 == -1) 
        diff = -1; 
       else 
        diff = index1.compareTo(index2); 
       // break if we found mismatch 
       if(diff != 0) break; 
      } 

      // return smaller string first in sort 
      if(diff == 0) 
       diff = len1.compareTo(len2); 
      return diff; 
     } 
    }; 

    // test client 
    public static void main(String[] args) { 
     List<String> list = new ArrayList<String>(); 
     list.add("ABCE1!4"); 
     list.add("ABCE1!7"); 
     list.add("!SDF"); 
     list.add("TRWESF!"); 
     Collections.sort(list, DiffSort.diffNaturalOrder); 

     // print sorted array 
     for(String s:list) 
      System.out.println(s); 
    } 
} 

/* ВЫВОД */

ABCE1! 4

ABCE1! 7

TRWESF!

! SDF

Answer 1

Поместите все персонажи order в Map<Character, Integer> (где целое число соответствует положению персонажа в order), а затем в вашем for -loop, вместо order.indexOf(c) использования map.get(c).

Вы можете настроить эту карту довольно легко:

private static final Map<Character, Integer> map = 
           new HashMap<Character, Integer>(order.length()); 

static { 
    for (int i = 0; i < order.length(); i++) 
     map.put(order.charAt(i), i); 
} 

Answer 2

Что я хотел бы сделать дополнительно, чтобы кэшировать вычисление положения выключения полукокса.

Первый w будет сравнивать, что символы равны перед проверкой на карте.

Тогда на карте будет храниться каждая комбинация символов.

(левый, правый)

, если не будет раньше, чем вернется 1 если право раньше, то вернуть -1 , если не эк право возврата 0.

Или вы могли бы обрешетка массив голец и под позиция char хранит заказ.

public final class CustomAlphabetComparator implements Comparator<String> { 

     private char order[] = new char[1<<16]; 


     public CustomAlphabetComparator (String alphabet) { 
      if (alphabet == null) throw new IllegalArgumentException("Input must not be null"); 

      char index = 0; 

      for(char c : alphabet.toCharArray()) { 
       order[c] = index++; 
      } 
     } 


     @Override 
     public int compare(String o1, String o2) { 

      if(o1 == o2) return 0; //We check the references 

      if(o1 == null && o2 == null) return 0; 
      if(o1 != null && o2 == null) return 1; 
      if(o1 == null && o2 != null) return -1; 

      if(o1.equals(o2)) return 0; //We check that are equal 

      char[] c1 = o1.toCharArray(); 
      char[] c2 = o2.toCharArray(); 

      int shortest = c1.length < c2.length ? c1.length : c2.length; 
      int result = 0; 

      for(int i = 0; result == 0 & i < shortest; i++) { 

       result = order[c1[i]] - order[c2[i]]; 

      } 

      return result; 
     } 

    } 

Answer 3

Очевидно, что код у вас есть работы, но одна вещь, чтобы иметь в виду, что String.indexOf (ч) проходит через символ строки по характеру, пока не найдет тот, он ищет. Если ваша строка находится ближе к концу вашего «алфавита», вы понесете много ненужных циклов.

Я хотел бы сохранить заказ в HashMap<Character, Integer> и вытащить информацию индексации из этого в постоянное время. Должно быть быстрее, чем цикл через всю строку (для каждого персонажа вы сравниваете!) ...

Answer 4

Вот эффективный Компаратор только заглавных букв английского алфавита (который может быть расширен, но не без ограничений):

public static Comparator<String> diffNaturalOrder = new Comparator<String>() { 
    private int[] order = new int[] {7, 9, 16, 22, 18, 24, 11, 8, 17, 4, 19, 25, 5, 14, 3, 21, 2, 0, 10, 15, 20, 6, 1, 13, 23, 12}; 
    public int compare(String v, String w) { 
     int diff = 0; 
     int len = Math.min(v.length(), w.length()); // lesser of 2 strings 
     int o1, o2; 
     for(int i=0; i<len; i++) { 
      o1 = order[v.charAt(i)-65]; 
      o2 = order[w.charAt(i)-65]; 
      diff = o1 - o2; 
      // break if we found mismatch 
      if(diff != 0) break; 
     } 
     if (diff == 0) { 
      diff = v.length() - w.length(); 
     } 
     return diff; 
    } 
}; 

Вместо indexOf или Map<Character, Integer> используется целочисленное значение символа (менее 65) для индексации в массив, содержащий данные упорядочения.Массив может быть сгенерирован как таковой:

private static void generateArray() { 
    String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL"; 
    int[] chars = new int[26]; 
    int i = 0; 
    for (char c : order.toCharArray()) { 
     chars[c-65] = i++; 
    } 
    System.out.println(Arrays.toString(chars)); 
}