-1

我被问到以下问题

There are X number of compressed files of different sizes in a single folder.
Where X is 1 to 250.
File size ranges from 1MB to 65MB. The compression ratio varies from 9 to 11.

There are Y number of parser threads. Where Y is between 1 to 8.

Write an application that distributes the files so each thread receives the same amount of data ( or as close as possible ).
Please follow all best coding practices and standards you are familiar with.

For example

If X is 5 and Y is 3 and the files are
File 1 is 1MB, File 2 is 2MB, File 3 is 3MB, File 4 = 4MB, File 5 = 5MB.

Uncompressed File 1,2,5 = compressed file * 9. Files 3,4 = compressed file * 10

Output
Thread <thread number> = Files <file number...> = <total size of all files uncompressed>
...
Data skew = ((max size - min size) / max size ) * 100

我是否认为这是一个不可能回答的问题，它似乎很模糊。在我看来，这是一个很难在 1 小时内回答的问题。

我认为分布并非微不足道。

编辑

我所知道的问题就是上面所说的。

对我来说，这似乎是一个非常模糊的问题。

4

1 回答 1

0

因此，根据我的评论，我认为这是传统的装箱问题的一个实例，除非在这种情况下，您提前知道一定数量的箱（线程）并且箱可以增长，这需要一些计算关闭。把它想象成有 X 个盒子，你必须用 Y 个项目填充，但盒子可以变得更高。

首先，我认为您需要预先计算未压缩的文件大小。未压缩的文件大小就像装箱问题中的“体积”。

接下来，我认为您根据未压缩的值对文件进行排序。这使得搜索列表更快。

为了实际将它们整理出来，请将线程视为装箱问题中的“垃圾箱”。我认为有很多方法可以做到这一点，在我确定一种特定方法之前，我会提出一个问题：你是否更关心首先使用所有线程，但让它们的大小尽可能接近可能，或者您是否更关心使结果尺寸尽可能接近，您不能使用比分配线程更多的东西？

如果关注的是使用所有线程，我认为我的方法看起来像：

  1. 从最大的文件开始，填满垃圾箱，使它们尽可能小。继续这样做，直到您不能再放入任何垃圾箱而不超过最大的垃圾箱（其中包含最大文件的垃圾箱）
  2. 将最小的物品放在最小的箱子里。这是你新的“水印”
  3. 与第 1 步一样，继续将最大的文件放在最大的垃圾箱中，以便在不超过水印的情况下接受它。继续这样做，直到你用完文件或者你不能在不超过的情况下再放入。如果是前者，你就完成了，如果是梯子，回到第 2 步。

相反，如果关注的是匹配大小，那么我的方法会有所不同。

  1. 把最大的物品放在最小的箱子里。这是你的“水印”。把它放在一边
  2. 抓住最小的垃圾箱。这是您当前工作的垃圾箱。
  3. 在不超过“水印”的情况下，找到适合您正在处理的垃圾箱的下一个最大的项目。
  4. 重复 #3 直到你无法填满当前的 bin
  5. 将最小的文件放在最小的 bin 中。这是你的新“水印”
  6. 只是为了#2

这里的好处是我认为你会得到一个非常均匀的分布，因为你总是让“箱子”尽可能地接近彼此的大小。问题在于它与垃圾箱的大小有关，而不是全部用完。

于 2013-03-28T12:54:53.857 回答