Trie 데이터 구조를 어떻게 사용하여 희소 행렬을 효율적으로 구현하고 기존 해시맵에 비해 더 빠른 읽기 전용 액세스와 최적화된 저장 공간을 제공할 수 있습니까?

희소 배열이라고도 알려진 희소 행렬은 대부분의 요소가 0이거나 정의되지 않은 행렬을 나타내는 데 사용되는 데이터 구조입니다. 기존 행렬과 달리 희소 행렬은 0이 아닌 요소만 저장하므로 0이 많은 대규모 행렬을 저장하는 데 효율적입니다.

해시맵을 사용하여 희소 행렬을 구현하는 것은 자주 읽는 데이터에 비효율적일 수 있습니다. 해시맵은 충돌을 유발하기 때문입니다. 읽기 및 쓰기 모두에 대해 각 후보 위치를 처리하고 소스 인덱스와 비교하려면 복잡한 해싱 함수와 루프가 필요합니다.

보다 효율적인 접근 방식은 직접 액세스가 가능한 Trie(Trie Radix Tree) 구조를 사용하는 것입니다. 세그먼트가 분산되는 단일 벡터로. 시도는 두 개의 배열 인덱싱 작업만으로 테이블에 요소가 있는지 확인할 수 있으며 빠른 읽기 전용 액세스와 기본값에 대한 백업 저장소의 기본 위치를 제공합니다.

이 접근 방식은 반환된 요소에 대한 테스트를 방지합니다. index는 모든 소스 인덱스가 최소한 백업 저장소의 기본 위치에 매핑되도록 보장하고 선택적인 "compact()" 작업을 사용하여 빠르게 업데이트 가능한 시도를 지원하여 여러 작업이 끝날 때 저장 공간을 최적화합니다.

시도는 복잡한 해싱 함수나 충돌 처리가 필요하지 않기 때문에 해시맵보다 훨씬 빠르며 Integer 및 Long 인덱스에 대해 Java IntegerTrieMap 및 LongTrieMap과 효율적으로 작동합니다. 단 이들은 현재 JRE에 포함되어 있지 않습니다.

예제 코드:

<code class="java">public class DoubleTrie {

    // Matrix options
    public static final int SIZE_I = 1024;
    public static final int SIZE_J = 1024;
    public static final double DEFAULT_VALUE = 0.0;

    // Internal splitting options
    private static final int SUBRANGEBITS_I = 4;
    private static final int SUBRANGEBITS_J = 4;

    // Internal derived splitting constants
    private static final int SUBRANGE_I = 1 << SUBRANGEBITS_I;
    private static final int SUBRANGE_J = 1 << SUBRANGEBITS_J;
    private static final int SUBRANGEMASK_I = SUBRANGE_I - 1;
    private static final int SUBRANGEMASK_J = SUBRANGE_J - 1;
    private static final int SUBRANGE_POSITIONS = SUBRANGE_I * SUBRANGE_J;

    // Internal derived default values for constructors
    private static final int SUBRANGES_I = (SIZE_I + SUBRANGE_I - 1) / SUBRANGE_I;
    private static final int SUBRANGES_J = (SIZE_J + SUBRANGE_J - 1) / SUBRANGE_J;
    private static final int SUBRANGES = SUBRANGES_I * SUBRANGES_J;
    private static final int DEFAULT_POSITIONS[] = new int[SUBRANGES];
    private static final double DEFAULT_VALUES[] = new double[SUBRANGE_POSITIONS](DEFAULT_VALUE);

    // Internal fast computations
    private static final int subrangeOf(int i, int j) {
        return (i >> SUBRANGEBITS_I) * SUBRANGE_J + (j >> SUBRANGEBITS_J);
    }
    private static final int positionOffsetOf(int i, int j) {
        return (i & SUBRANGEMASK_I) * SUBRANGE_J + (j & SUBRANGEMASK_J);
    }

    // Internal member variables
    private double values[];
    private int subrangePositions[];
    private boolean isSharedValues;
    private boolean isSharedSubrangePositions;

    // Internal method
    private final void reset(double[] values, int[] subrangePositions) {
        this.isSharedValues = (this.values = values) == DEFAULT_VALUES;
        this.isSharedSubrangePositions = (this.subrangePositions = subrangePositions) == DEFAULT_POSITIONS;
    }

    // Reset method
    public void reset(double initialValue = DEFAULT_VALUE) {
        reset((initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES : new double[SUBRANGE_POSITIONS](initialValue), DEFAULT_POSITIONS);
    }

    // Default constructor
    public DoubleTrie(double initialValue = DEFAULT_VALUE) {
        this.reset(initialValue);
    }

    // Immutable default instance
    public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie();

    // Copy constructor
    public DoubleTrie(DoubleTrie source) {
        this.values = (this.isSharedValues = source.isSharedValues) ? source.values : source.values.clone();
        this.subrangePositions = (this.isSharedSubrangePositions = source.isSharedSubrangePositions) ? source.subrangePositions : source.subrangePositions.clone();
    }

    // Fast indexed getter
    public double getAt(int i, int j) {
        return values[subrangePositions[subrangeOf(i, j)] + positionOffsetOf(i, j)];
    }

    // Fast indexed setter
    public double setAt(int i, int j, double value) {
        int subrange = subrangeOf(i, j);
        int positionOffset = positionOffsetOf(i, j);

        // Check if the assignment will change anything
        int subrangePosition, valuePosition;
        if (Double.compare(values[valuePosition = (subrangePosition = subrangePositions[subrange]) + positionOffset], value) != 0) {
            // The assignment will change something, check if the affected subrange is shared

            if (isSharedValues) {
                values = values.clone();
                isSharedValues = false;
            }

            // Scan all other subranges to check if the affected position is shared

            for (int otherSubrange = subrangePositions.length; --otherSubrange >= 0;) {
                if (otherSubrange != subrange) {
                    continue; // Ignore the target subrange
                }

                // Check if the target position is shared by another subrange

                if ((otherSubrangePosition = subrangePositions[otherSubrange]) >= valuePosition && otherSubrangePosition + SUBRANGE_POSITIONS < valuePosition) {
                    // The target position is shared, we need to make it unique by cloning the subrange and copying all its values to the end of the new vector

                    if (isSharedSubrangePositions) {
                        subrangePositions = subrangePositions.clone();
                        isSharedSubrangePositions = false;
                    }

                    values = DoubleTrie.arraysetlength(values, (subrangePositions[subrange] = subrangePositions = values.length) + SUBRANGE_POSITIONS);
                    valuePosition = subrangePositions + positionOffset;
                    break;
                }
            }

            // Assign the new value

            values[valuePosition] = value;
        }

        return value;
    }

    // Compact storage method
    public void compact() {
        int oldValuesLength = values.length;
        int newValuesLength = 0;

        for (int oldPosition = 0; oldPosition < oldValuesLength; oldPosition += SUBRANGE_POSITIONS) {
            int oldPosition = positions[subrange];
            boolean commonSubrange = false;

            // Scan values for possible common subranges

            for (int newPosition = newValuesLength; (newPosition -= SUBRANGE_POSITIONS) >= 0;) {
                if (arrayequals(values, newPosition, oldPosition, SUBRANGE_POSITIONS)) {
                    commonSubrange = true;

                    // Update the subrangePositions with all matching positions from oldPosition to newPosition

                    for (subrange = subrangePositions.length; --subrange >= 0;) {
                        if (subrangePositions[subrange] == oldPosition) {
                            subrangePositions[subrange] = newPosition;
                        }
                    }

                    break;
                }
            }

            if (!commonSubrange) {
                // Move down the non-common values

                if (!commonSubrange && oldPosition != newValuesLength) {
                    DoubleTrie.arraycopy(values, oldPosition, newValuesLength, SUBRANGE_POSITIONS);
                    newValuesLength += SUBRANGE_POSITIONS;
                }
            }
        }

        // Check the number of compressed values

        if (newValuesLength < oldValuesLength) {
            values = values.arraysetlength(newValuesLength);
            isSharedValues = false;
        }
    }
}</code>

위 내용은 Trie 데이터 구조를 어떻게 사용하여 희소 행렬을 효율적으로 구현하고 기존 해시맵에 비해 더 빠른 읽기 전용 액세스와 최적화된 저장 공간을 제공할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!