알파벳 순서에 따라 문자열 ' "순열"을 찾습니다.

Question

아래 코드와 같이 알파벳 순서에 따라 문자열의 순열을 찾는 더 효율적인 방법이 있다면 조언을 구합니다. 최대 16 자까지 문자열을 처리하고 있으며 많은 양의 데이터가 필요하며 프로그램을 실행하는 데 너무 많은 시간과 메모리가 필요합니다. 문제의

기본 표현

입력 : 알파벳

출력 : 그래서 단어 "알파벳"편지에서

'는'알파벳의 첫 번째 16752348, 그것을 인덱스 1을 표시, 그런 다음 다섯 번째 위치에 다른 'a'가오고 2로 표시 한 다음 여섯 번째 위치에 'b'가오고 3 등으로 표시합니다.

코드에서 숫자 대신 색인을 사용합니다. of, 나는 ASCII 값의 65라는 문자를 사용한다. (왜냐하면 나는 긴 문자열을 테스트하기 때문에,하지만 주요 목적은 바뀌지 않는다.) 알파벳

출력 : AFGEBCDH

public static String perm(String word){ 

    char[] perm = new char[word.length()]; 
    char[] wordArray = word.toCharArray(); 
    char[] sortedWord = new char[word.length()]; 

    sortedWord = word.toCharArray(); 
    Arrays.sort(sortedWord); 

    for (int i=0; i<word.length(); i++){ 
     for (int j=0; j<word.length(); j++){ 

      if (sortedWord[i] == wordArray[j]){ 
       perm[j] = (char)(65+i); //from A 
       wordArray[j] = '.'; 

       j = word.length(); //in case, if the word has more of the tested char, we jump to the end of the cycle 
      } 
     } 
    } 

    return String.valueOf(perm); 
} 

public static void main (String [] args){ 
    System.out.println(perm("alphabet")); 
} 

Answer 1

필자의 이전 솔루션을 살펴보면 Arrays.sort()와 비슷한 배열은 기본 유형의 배열보다 훨씬 오래 걸립니다. 나는 몇 가지 더 접근을 시도하고, 다음 큰 단어의 수를 작은 시간을 준 하나입니다 접근 단어 만의 하위 15 비트를 사용하는 것이 암시 적 가정을 만드는 것을

가

public static String perm(String word){ 
    int l = word.length(); 
    int[] els = new int[l]; 
    for (int i=0; i<l; i++) { 
     els[i] = (word.charAt(i) << 16) | i; 
    } 
    Arrays.sort(els); 
    char[] sb = new char[l]; 
    for (int i=0; i<els.length; i++) { 
     sb[i] = (char)('A' + els[i] & 0xFFFF); 
    } 
    return String.valueOf(sb); 
    } 

주 UTF-16 인코딩 (영어 알파벳의 단어에 해당).

메모리 사용 측면에서 Java로 측정 한 것에 대해주의해야합니다. 하나의 접근법에서 다른 접근법으로 메모리 사용이 급증 할 수 있다는 사실은 메모리가 가비지 수집 될 수 있으므로 반드시 좋은 지표는 아닙니다. 여기의 모든 접근법은 perm()이 실행 된 후에 가비지 콜렉션에서 사용할 수있는 임시 배열/객체를 사용합니다 (반환 된 문자열 제외). 자, 가비지 콜렉션을 줄이기 위해 (그리고 성능을 향상시키기 위해) 메모리 사용을 줄이는 것에 관심이 있다면, 나는 이것을 측정하지는 않았지만,이 마지막 접근법이 좋은 결과를 가져야한다고 생각합니다.

Answer 2

WRT의 메모리 사용률, 붙여 넣은 프로그램이 많이 사용하지 않습니다 그래서 내 프로그램의 출력은

가 입력됩니다. 실제 코드에서 반환 된 문자열로 무엇을하고 있습니까?

지금까지 성능이가는대로,이 조금 더 나은한다 :

import java.util.Arrays; 

class El implements Comparable<El>{ 
char c; 
int idx; 

public El(char c, int idx) { 
    this.c = c; 
    this.idx = idx; 
} 

public int compareTo(El other) { 
    return Character.compare(c, other.c); 
} 
} 

public class Perm { 
    public static String perm(String word){ 
    int l = word.length(); 
    El[] els = new El[l]; 
    for (int i=0; i<l; i++) { 
     els[i] = new El(word.charAt(i), i); 
    } 
    Arrays.sort(els); 
    StringBuilder sb = new StringBuilder(l); 
    for (int i=0; i<els.length; i++) { 
     sb.append((char)('A' + els[i].idx)); 
    } 
    return sb.toString(); 
    } 

    public static void main (String [] args){ 
    System.out.println(perm("alphabet")); 
    } 
} 

Answer 3

이 시도 :

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class alphabet { 
    public static List<CharIndexHolder> charlist = new ArrayList<CharIndexHolder>(); 

    public static String perm(String word) { 
     char[] perm = new char[word.length()]; 
     char[] wordArray = word.toCharArray(); 
     char[] sortedWord = new char[word.length()]; 

     sortedWord = word.toCharArray(); 
     Arrays.sort(sortedWord); 

     for (int i=0; i<word.length(); i++){ 
      for (int j=0; j<word.length(); j++){ 

       if (sortedWord[i] == wordArray[j]){ 
        perm[j] = (char)(65+i); //from A 
        wordArray[j] = '.'; 

        j = word.length(); //in case, if the word has more of the tested char, we jump to the end of the cycle 
       } 
      } 
     } 
     return String.valueOf(perm); 
    } 

    public static String perm2(String word) { 
     charlist.clear(); 
     for(int i = 0; i < word.length(); i++) { 
      charlist.add(new CharIndexHolder(word.charAt(i), i)); 
     } 
     Collections.sort(charlist); 
     for(int i = 0; i < charlist.size(); i++) { 
      charlist.get(i).assignedindex = i; 
     } 
     char[] result = new char[word.length()]; 
     for(int i = 0; i < result.length; i++) { 
      CharIndexHolder cur = charlist.get(i); 
      result[cur.index] =(char) (charlist.get(i).assignedindex + 65); 
     } 
     return new String(result); 
    } 

    public static void main (String [] args){ 
     System.out.println(perm("alphabet")); 
     System.out.println(perm2("alphabet")); 
    } 
} 

도우미 클래스 :

public class CharIndexHolder implements Comparable<CharIndexHolder> { 
    public int index; 
    private char character; 
    public int assignedindex; 

    CharIndexHolder(Character character, int index) { 
     this.character = character; 
     this.index = index; 
    } 

    @Override 
    public int compareTo(CharIndexHolder o) { 
     if(this.character < o.character) { 
      return -1; 
     } 
     if(this.character > o.character) { 
      return 1; 
     } 
     if(this.index < o.index) { 
      return -1; 
     } 
     if(this.index > o.index) { 
      return 1; 
     } 
     return 0; 
    }  
} 

내가 생각할 수 없다 N * log (n)보다 빠르게 진행하는 방법. 속도가 더 필요하면 목록을 긴 배열로 바꾸고 배열 당 할당을 한 번만 수행하십시오 (호출 당 한 번이 아님).