java - 如何有效地按组对列表进行排序？

Question

我需要通过一些给定的元素“ block ”或“组”对给定的排序列表进行分组。例如:

给定一个列表:

[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]

元素 block 不能与非组元素混合。这些 block 应该具有相同的顺序。列表的其他元素应保持其顺序。

---

我已经找到解决办法了。但这并不是您将看到的最有效的代码。

我也在使用 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.002s 0.129s

12000 0.021s 14.673s

Answer 1

从您提交的代码中，我无法弄清楚您的算法是如何完全工作的。

我可以编写另一个算法来完成该任务。

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]
   

时间复杂度与排序算法相同