最適化された機能

自分のレポートを組み合わせて管理できるWebを開発しています.
したがって、ログインするたびに、独自のレポートを取得し、既存のdb上のレポートと同期する必要があります.
この部分では,既存のコードの時間的複雑度はO(N*M)である.
そのため、私たちはこの点を改善する必要があると思って、最適化の仕事を始めました.
既存のコードは次のとおりです.

    private void _syncRepositoryDelete(List<GithubRepositoryRequest> newlyRepositories,
                                      List<GithubRepository> repositories,
                                      List<GithubRepositorySyncModel> sync) {
        for(GithubRepository repository : repositories) {
            boolean isExists = false;

            for(GithubRepositoryRequest newly : newlyRepositories) {
                if(newly.getRepositoryName().equals(repository.getRepositoryName())) {
                    isExists = true;
                }
            }

            if(!isExists) {
                sync.add(new GithubRepositorySyncModel(repository, true, false));
            }
        }
    }

    private void _syncRepositoryAdd(List<GithubRepositoryRequest> newlyRepositories,
                                    List<GithubRepository> repositories,
                                    List<GithubRepositorySyncModel> sync) {
        for(GithubRepositoryRequest newly : newlyRepositories) {
            boolean isExists = false;

            for(GithubRepository repository : repositories) {
                if(repository.getRepositoryName().equals(newly.getRepositoryName())) {
                    isExists = true;
                    sync.add(new GithubRepositorySyncModel(repository, false, true));
                    break;
                }
            }

            if(!isExists) {
                sync.add(new GithubRepositorySyncModel(newly.toEntity(), false, true));
            }
        }
    }

はい.非効率なターミネーターを示した
だから、O(N*M)コードをO(N)に改善する方法を考えています.
資料構造LinkedListを利用すれば良いと思います
したがって、リンクリストに2つのデータ(既存dbデータ、新しく入力した既存dbと同期する必要があるデータ)を配置し、ソート基準をリポジトリ名とソートすると、既存データと同期するため、コードが記述される.
(以前はPriorityQueueを使用しようとしたが、データが移動すると並べ替えられ、LinkedListに入れて並べ替えられるため、データを削除するたびにPriorityQueueはLinkedListよりも遅く並べ替えられる.)
LinkedListは、データを挿入または削除する際にノード上のポインタを変更するだけでよいので、poll()、add()はO(1)に非常に迅速に挿入および削除することができる.
だからLinkedListを使うことにしました

    /**
     * O(N) sync
     * @param objects1 기존 배열
     * @param objects2 새로운 배열
     * */
    private static List<Object> syncArray(LinkedList<Object> objects1, LinkedList<Object> objects2) {
        List<Object> result = new ArrayList<>();
        List<Object> deleted = new ArrayList<>();
        int olderSize = objects1.size();
        int newlySize = objects2.size();

        while(!objects1.isEmpty()) {
            Object obj1 = objects1.peek();
            Object obj2 = objects2.peek();

            if(obj1.equals(obj2)) {
                objects1.poll();
                objects2.poll();
                result.add(obj1);
            }
            else {
                if (newlySize > olderSize) {
                    result.add(objects2.poll());
                }
                else {
                    deleted.add(objects1.poll());
                }
            }
        }

        return result;
    }

「結果」(Results)リストには、追加する新しい値のみが含まれます.
削除された配列には、削除する値が含まれます.

既存のコードのパフォーマンスのテスト

既存データ(N)=10000000
データの追加/データの削除(M)=100001/99999

    private static void _syncRepositoryDelete(Object[] objects1, Object[] objects2, List<Object> sync) {
        for(Object repository : objects1) {
            boolean isExists = false;

            for(Object newly : objects2) {
                if(newly.equals(repository)) {
                    isExists = true;
                }
            }

            if(!isExists) {
                sync.add(repository);
            }
        }
    }

    private static void _syncRepositoryAdd(Object[] newlyRepositories,
                                    Object[] repositories,
                                    List<Object> sync) {
        for(Object newly : newlyRepositories) {
            boolean isExists = false;

            for(Object repository : repositories) {
                if(repository.equals(newly)) {
                    isExists = true;
                    sync.add(repository);
                    break;
                }
            }

            if(!isExists) {
                sync.add(newly);
            }
        }
    }

これらのパラメータのみを変更し、テスト用のコードを作成し、既存のコードをテストしました.それぞれの追加と削除をテストしました.

既存のアルゴリズム-結果1(リモート・リポジトリでデータが作成されている場合)

≪既存のアルゴリズム｜Existing Algorithm｜Eas≫-結果2(リモート・ストレージから1つのデータが削除されました)

非常に惨憺たる結果だった
ユーザーは100000個のレジストリを持っていないかもしれませんが、100個以上のレジストリを持っていると、サービスを使用するのは非常に不便です.さらにspringbootコードでは、これらのデータを同期してdbに入れる必要があります.これにより、より遅くなります.
改善されたコードと速度を公開します.

コードパフォーマンスの向上テスト

    /**
     * O(N) sync
     * @param objects1 기존 배열
     * @param objects2 새로운 배열
     * */
    private static List<Object> syncArray(LinkedList<Object> objects1, LinkedList<Object> objects2) {
        List<Object> result = new ArrayList<>();
        List<Object> deleted = new ArrayList<>();
        int olderSize = objects1.size();
        int newlySize = objects2.size();

        while(!objects1.isEmpty()) {
            Object obj1 = objects1.peek();
            Object obj2 = objects2.peek();

            if(obj1.equals(obj2)) {
                objects1.poll();
                objects2.poll();
                result.add(obj1);
            }
            else {
                if (newlySize > olderSize) {
                    result.add(objects2.poll());
                }
                else {
                    deleted.add(objects1.poll());
                }
            }
        }

        return result;
    }

改善されたアルゴリズム結果1-(リモート・リポジトリでデータが作成された場合)

改善されたアルゴリズム結果2-(リモートストレージからデータが削除されました)

コードショーがかなり上がっているのが見えます
45266ms -> 24ms
45576ms -> 29ms
性能は約1728.5倍向上した.

改良後に適用されるspring-bootコード

    private Map<String, List<GithubRepository>> sync(List<GithubRepository> newly, List<GithubRepository> older) {
        LinkedList<GithubRepository> olderQueue = toRepositorySorted(older);
        LinkedList<GithubRepository> newlyQueue = toRepositorySorted(newly);
        List<GithubRepository> result = new ArrayList<>(); // 추가할 것
        List<GithubRepository> deleted = new ArrayList<>(); // 삭제할 것
        Map<String, List<GithubRepository>> resultMap = new HashMap<>(); // sync 결과 맵
        int newlySize = newlyQueue.size();
        int olderSize = olderQueue.size();

        //기존에 있던 큐들의 싱크를 맞춰주고 삭제할 것들을 추가해주는 작업
        while(!olderQueue.isEmpty()) {
            GithubRepository newlyRepository = newlyQueue.peek();
            GithubRepository olderRepository = olderQueue.peek();

            // 기존에 있었던 레포지토리이므로 큐에서 삭제
            if(newlyRepository.getRepositoryName().equals(olderRepository.getRepositoryName())) {
                newlyQueue.poll();
                olderQueue.poll();
            }
            else {
                if(newlySize > olderSize) {
                    result.add(newlyQueue.poll());
                }
                else {
                    deleted.add(olderQueue.poll());
                }
            }
        }
        resultMap.put("adding", result);
        resultMap.put("delete", deleted);

        return resultMap;
    }

    @Transactional
    public void syncRepository(List<GithubRepository> newlyRepositories, Long ownerId) {
        List<GithubRepository> repositories = repositoryCrud.findByOwner(ownerId);
        Map<String, List<GithubRepository>> resultMap = sync(newlyRepositories, repositories);
        List<GithubRepository> addRepositoryList = resultMap.get("adding");
        List<GithubRepository> deleteRepositoryList = resultMap.get("delete");

        for(GithubRepository addRepository : addRepositoryList) {
            repositoryCrud.save(addRepository);
        }
        for(GithubRepository deleteRepository : deleteRepositoryList) {
            repositoryCrud.deleteById(deleteRepository.getId());
        }
    }

この仕事をしているうちに、基本功の重要性を改めて認識しました.データ構造を適切に使用すると、コードのパフォーマンスが向上します.