Разделить сортировку на группы (от A до E, от F до J ....) с помощью java

Question

У меня есть отсортированный по алфавиту arraylist, который я должен разбить на 5 наборов. Использование Java - набор 1, содержащий список слов между A и E - набор 2, содержащий список слов между F и J - набор 3, содержащий список слов между K и O - набор 4, содержащий список слов между P и T - набор 5, содержащий список слов между U и Z

Может ли кто-нибудь сообщить мне эффективный метод для этого. Я использую Java 8.

Спасибо, Tushar

Answer 1

Если начать с отсортированного списка, в котором все элементы гарантированно начать с простого прописной буквы (т.е. A-Z), когда наиболее производительность эффективной способ заключается в использовании binarySearch() и subList().

Производительность O (log n) от binarySearch().

List<String> list = Arrays.asList("Actually", "Chalk", "Dramatic", "Fence", "Horrible", "Labored", 
            "Resonant", "Six", "Slap", "Spark", "Tin", "Treatment"); 
int idxF = Collections.binarySearch(list, "F"); 
int idxK = Collections.binarySearch(list, "K"); 
int idxP = Collections.binarySearch(list, "P"); 
int idxU = Collections.binarySearch(list, "U"); 
if (idxF < 0) idxF = ~idxF; 
if (idxK < 0) idxK = ~idxK; 
if (idxP < 0) idxP = ~idxP; 
if (idxU < 0) idxU = ~idxU; 
List<String> listA_E = list.subList(0, idxF); 
List<String> listF_J = list.subList(idxF, idxK); 
List<String> listK_O = list.subList(idxK, idxP); 
List<String> listP_T = list.subList(idxP, idxU); 
List<String> listU_Z = list.subList(idxU, list.size()); 
System.out.println(listA_E); 
System.out.println(listF_J); 
System.out.println(listK_O); 
System.out.println(listP_T); 
System.out.println(listU_Z); 

Выход

[Actually, Chalk, Dramatic] 
[Fence, Horrible] 
[Labored] 
[Resonant, Six, Slap, Spark, Tin, Treatment] 
[] 

---

Если вы начинаете с несортированным списка, наиболее эффективный способ сделать это, чтобы создать Map<Group, List<String>> где Group представляет собой уникальное значение, представляющее группу. Это может быть простой Character для первого символа группы (A, F, K, P, U) или какой-либо другой класс, например. a enum.

Производительность O (n log n) от TreeMap/TreeSet здание.

enum LetterGroup { 
    A_E, F_J, K_O, P_T, U_Z; 
    public static LetterGroup of(String s) { 
     char ch = Character.toUpperCase(s.charAt(0)); 
     if (ch >= 'A' && ch <= 'E') return A_E; 
     if (ch >= 'F' && ch <= 'J') return F_J; 
     if (ch >= 'K' && ch <= 'O') return K_O; 
     if (ch >= 'P' && ch <= 'T') return P_T; 
     if (ch >= 'U' && ch <= 'Z') return U_Z; 
     throw new IllegalArgumentException(s); 
    } 
} 

С переименованием, вы можете сделать это, используя Java 8 Streams.

List<String> list = Arrays.asList("dramatic","slap","chalk","fence","resonant","tin", 
            "six","labored","spark","treatment","horrible","actually"); 
Map<LetterGroup, Set<String>> groups = list.stream() 
              .collect(Collectors.groupingBy(LetterGroup::of, 
                      TreeMap::new, 
                      Collectors.toCollection(TreeSet::new))); 
for (Entry<LetterGroup, Set<String>> entry : groups.entrySet()) 
    System.out.println(entry); 

Выход

A_E=[actually, chalk, dramatic] 
F_J=[fence, horrible] 
K_O=[labored] 
P_T=[resonant, six, slap, spark, tin, treatment] 

Answer 2

Вам нужно какое-то функции квалификационных и перечисление, например (Псевдокод):

enum Scope{AE, FJ, //... 

    static Scope inScope(String s){ 
     return Arrays.asStream(Scope.values()) 
      .stream().filter(s -> isInScope(s)).findFirst().get(); 
    } 
    abstract boolean isInScope(String word); 
} 

Function<String, Scope> f = Scope::inScope; 
// in code 
listOfWords.stream().groupBy(f).values(); 

Scope перечисление определяет группы по буквам. В методе isInScope вы проверяете данное слово в области. Функция f - это просто ярлык. Последняя строка - это операция группировки слов по областям, которая дает вам Map<Scope, List<String>> и извлекает значения.

Общая идея заключается в том, что у вас есть groupBy сборщик в стандартном API. Им нужна функция классификатора. Эта функция может быть связью if или, как в моем примере, перечислением.

Answer 3

Самое простое решение, которое работает для не отсортированных списка

Map<Integer, List<String>> m = list.stream() 
    .collect(Collectors.groupingBy(s->Math.min((s.charAt(0)-'A'&~32)/5,4))); 

// the keys range from 0 to 4, as can be shown with: 
System.out.println("a-e: "+m.getOrDefault(0, Collections.emptyList())); 
System.out.println("f-j: "+m.getOrDefault(1, Collections.emptyList())); 
System.out.println("k-o: "+m.getOrDefault(2, Collections.emptyList())); 
System.out.println("p-t: "+m.getOrDefault(3, Collections.emptyList())); 
System.out.println("u-z: "+m.getOrDefault(4, Collections.emptyList())); 

Если вы считаете, используя карту вместо проведения пять коллекций later- вместо этого вы можете использовать симпатичные клавиши печати:

String[] key={"a-e", "f-j", "k-o", "p-t", "u-z" }; 
Map<String, List<String>> m = list.stream() 
    .collect(Collectors.groupingBy(s->key[Math.min((s.charAt(0)-'A'&~32)/5,4)])); 

for(String k:key) System.out.println(k+": "+m.getOrDefault(k, Collections.emptyList())); 

Конечно, этот код также работает для отсортированных списков, но тогда он не использует отсортированную природу. Использование сортировки для эффективности требует использования бинарного поиска или аналогичных методов, как показано на рисунке Andreas’ answer. Конечно, это немного сложнее для кода, чем одна операция groupingBy ...