Как эффективно отсортировать список по группам?

Question

Мне нужно сгруппировать данный список сортировки по некоторым заданным «блокам» или «группам» элементов.Например:

Дан список:

[A, B, C, D, E, F, G, H, I, J]

И группы

[A, C, D]
[F, E]
[J, H, I]

результат должен быть

[A, C, D, B, F, E, G, J, H, I]

Блоки элементовнельзя смешивать с элементами, не относящимися к группе.Блоки должны иметь одинаковый порядок.Другие элементы списка должны поддерживать свой порядок.

---

Я уже нашел решение.Но это не самый эффективный код, как вы увидите.

Я также использую java 6 ...

public static List<CategoryProduct> sortProductsByBlocks(List<CategoryProduct> products, CategoryBlocks categoryBlocks) {
    if (!validateCategoryBlocks(categoryBlocks)) {
        return products;
    }
    Map<String, BlockView> mapProductByBlock = mapBlocksByPartnumber(categoryBlocks);
    Map<String, BlockView> mapFirstProductByBlock = mapFirstProductByBlock(categoryBlocks);
    Map<Integer, Block> blocksById = blocksById(categoryBlocks);
    List<CategoryProduct> sortedProduct = Lists.newArrayList();
    Map<String, CategoryProduct> productsMapByPartNumber = ProductHelper.getProductsMapByPartNumber(products);
    List<CategoryProduct> processedProducts = Lists.newArrayList();
    int j = 0;
    for (int i = 0; i < products.size(); i++) {
        CategoryProduct product = products.get(i);
        if (blocksById.isEmpty() && !processedProducts.contains(product)) {
            sortedProduct.add(j++, product);
            processedProducts.add(product);
        }
        if (!processedProducts.contains(product) && (mapFirstProductByBlock.get(product.getPartNumber()) != null
                || mapProductByBlock.get(product.getPartNumber()) == null)) {
            BlockView blockView = mapProductByBlock.get(product.getPartNumber());
            if (blockView != null) {
                Block block = blocksById.get(blockView.getBlockId());
                if (block == null) {
                    sortedProduct.add(j++, product);
                    continue;
                }
                for (BlockProduct blockProduct : block.getProducts()) {
                    CategoryProduct categoryProduct = productsMapByPartNumber.get(blockProduct.getPartnumber());
                    sortedProduct.add(j++, categoryProduct);
                    processedProducts.add(categoryProduct);
                }
                blocksById.remove(blockView.getBlockId());
            } else {
                sortedProduct.add(j++, product);
                processedProducts.add(product);
            }
        }
    }

    return sortedProduct;
}

---

Любой совет по улучшению и ускорению будетдобро пожаловать.

(редактировать с улучшенным кодом)

public static List<CategoryProduct> sortProductsByBlocks2(List<CategoryProduct> products,
        CategoryBlocks categoryBlocks) {
    if (!validateCategoryBlocks(categoryBlocks)) {
        return products;
    }

    Map<String, Integer> blocksIdByFirstPartnumber = Maps.newHashMap();
    List<String> partnumbersInBlocks = Lists.newArrayList();
    for (int k = 0; k < categoryBlocks.getBlocks().size(); k++) {
        Block block = categoryBlocks.getBlocks().get(k);
        if (block != null && block.getProducts() != null) {
            for (int i = 0; i < block.getProducts().size(); i++) {
                BlockProduct blockProduct = block.getProducts().get(i);
                if (i == 0) {
                    blocksIdByFirstPartnumber.put(blockProduct.getPartnumber(), k);
                } else {
                    partnumbersInBlocks.add(blockProduct.getPartnumber());
                }
            }
        }
    }

    CategoryProduct[] result = new CategoryProduct[products.size()];
    Map<String, Integer> productsIndex = Maps.newHashMap();
    Map<String, CategoryProduct> categoryProductByPartnumber = Maps.newHashMap();
    int indexResult = 0;
    for (CategoryProduct categoryProduct : products) {
        String partNumber = categoryProduct.getPartNumber();
        if (!partnumbersInBlocks.contains(partNumber)) {
            if (blocksIdByFirstPartnumber.get(partNumber) != null) {
                Block categoryProductBlock = categoryBlocks.getBlocks()
                        .get(blocksIdByFirstPartnumber.get(partNumber));
                result[indexResult] = categoryProduct;
                indexResult++;
                for (int i = 1; i < categoryProductBlock.getProducts().size(); i++) {
                    BlockProduct blockProduct = categoryProductBlock.getProducts().get(i);
                    if (categoryProductByPartnumber.get(blockProduct.getPartnumber()) != null) {
                        result[indexResult] = categoryProductByPartnumber.get(blockProduct.getPartnumber());
                    } else {
                        productsIndex.put(blockProduct.getPartnumber(), indexResult);
                        result[indexResult] = null;
                    }
                    indexResult++;
                }
            } else {
                result[indexResult] = categoryProduct;
                indexResult++;
            }
        } else {
            if (productsIndex.get(partNumber) != null) {
                result[productsIndex.get(partNumber)] = categoryProduct;
            } else {
                categoryProductByPartnumber.put(partNumber, categoryProduct);
            }
        }
    }
    return Lists.newArrayList(Arrays.asList(result));
}

Производительность:

Элементы Новый алгоритм Старый алгоритм

1200 0,002 с 0,129 с

12000 0,021 с 14,673 с

Answer 1

По вашему определению не совсем понятно, каковы условия объединения результатов из вашего заданного списка и «групп» (массивов). Тем не менее, вот решение, основанное на ваших требованиях, использующее утверждение

"Вы хотите, чтобы первый элемент списка не содержался ни в одной из групп, вставленных между группами ..."

public class MergeArrays {

    private static final List<String> FIRST = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J"));
    private static final List<String> SECOND = new ArrayList<>(Arrays.asList("A", "C", "D"));
    private static final List<String> THIRD = new ArrayList<>(Arrays.asList("F", "E"));
    private static final List<String> FOURTH = new ArrayList<>(Arrays.asList("J", "H", "I"));

    public static List<String> merge(List<String> source, List<String>... lists) {
        List<String> result = new ArrayList<>();
        for (List<String> list : lists) {
            for (String value : list) {
                source.remove(value);
            }
        }

        for (List<String> list : lists) {
            String value = null;
            if (source.size() > 0) {
                value = source.get(0);
                source.remove(0);
            }
            result.addAll(merge(value, list));
        }
        return result;
    }

    public static List<String> merge(String value, List<String> list) {
        List<String> result = new ArrayList<>(list);
        if (value != null) {
            result.add(value);
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> result = merge(FIRST, SECOND, THIRD, FOURTH);
        System.out.println(result);
    }
}

// Результаты

[A, C, D, B, F, E, G, J, H, I]

Answer 2

Сформируйте код, который вы отправили, я не могу понять, как работает ваш алгоритм.

Я могу написать другой алгоритм, который будет выполнять задачу.

1. Отметить первый элемент для каждой группы

   [A,C,D] -> A
   

2. Удалить из list(to_be_sorted) все элементы из групп, которые не отмечены

   [A,C,D] -> remove [C,D]
   

3. выполнить сортировку по списку

   result ([A,B,F,G,J])
   

4. разместить удаленный элемент на основе знака

   Initial Sorted List [A,B,F,G,J]
   A->add [C,D]
   List is [A,C,D,B,F,G,J]
   B->as it is
   F->add [E]
   List is [A,C,D,B,F,E,G,J]
   G->as it is
   J->add [H,I]
   Final Sorted List [A,C,D,B,F,E,G,J,H,I]
   

Сложность по времени аналогична алгоритму сортировки