标签: bucket-sort

我正在阅读基数,计数和桶排序的定义,似乎所有这些都只是下面的代码:

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

我知道我不对,所以我错过了什么？如果您认为可以帮助解释Java或C,请显示代码

这个评论表明我的O(n log n)解决方案有一个O(n)替代方案来解决这个问题:

鉴于string str("helloWorld")预期的产出是:

l = 3
o = 2

我的解决方案是这样做:

sort(begin(str), end(str));

for(auto start = adjacent_find(cbegin(str), cend(str)), finish = upper_bound(start, cend(str), *start); start != cend(str); start = adjacent_find(finish, cend(str)), finish = upper_bound(start, cend(str), *start)) {
   cout << *start << " = " << distance(start, finish) << endl;
}

这显然受到排序的限制str.我认为这需要一个桶排序解决方案？有什么比我更缺的聪明吗？

我刚读了关于Bucket sort的Wikipedia页面.在本文中,他们说最坏的情况是O(n²).但我认为最坏的情况复杂性是O(n + k),其中k是桶的数量.这就是我计算这种复杂性的方法:

1. 将元素添加到存储桶.使用链表这是O(1)
2. 浏览列表并将元素放入正确的存储桶= O(n)
3. 合并桶= O(k)
4. O(1)*O(n)+ O(k)= O(n + k)

我错过了什么吗？

让A1,A2,...,An介于实数[0,2k](k为常数).据了解,对于任何一对Ai,AJ随后|Ai-Aj|>=k/n,

描述在O(n)运行时最坏情况下对数字进行排序的算法.

我知道答案应该是桶式的.无法理解为什么,如果是这样,我如何选择正确数量的水桶？如何在|Ai-Aj|>=k/n实际上帮助？

对于当前的OpenCL GPGPU项目,我需要根据具有64个可能值的某个键对数组中的元素进行排序.我需要最后一个数组让所有具有相同键的元素都是连续的.将关联数组new_index[old_index]作为此任务的输出就足够了.

我把任务分成两部分.首先,我计算每个可能的密钥(桶)使用此密钥(进入该桶)的元素数量.我扫描这个数组(生成一个前缀和),它指示每个桶的元素的新索引范围,例如每个桶的"开始"索引.

然后,第二步必须为每个元素分配一个新索引.如果我要在CPU上实现它,算法将是这样的:

for all elements e:
    new_index[e] = bucket_start[bucket(e)]++

当然,这在GPU上不起作用.每个项目都需要以bucket_start读写模式访问数组,这实际上是所有工作项之间的同步,这是我们能做的最糟糕的事情.

一个想法是在工作组中进行一些计算.但我不确定应该如何完成,因为我没有GPGPU计算经验.

在全局内存中,我们使用前缀sum初始化了bucket start数组,如上所述.使用原子int"访问"此数组的"互斥".(我是新来的,所以也许在这里混合一些词.)

每个工作组都隐式分配了输入元素数组的一部分.它使用包含新索引的本地存储桶数组,相对于我们尚不知道的(全局)存储桶启动.在其中一个"本地缓冲区"已满后,工作组必须将本地缓冲区写入全局数组.为此,它锁定对全局存储区启动数组的访问,将这些值递增当前本地存储区大小,解锁,然后将结果写入全局new_index数组(通过添加相应的偏移量).重复此过程,直到处理完所有已分配的元素.

出现两个问题:

1. 这是一个好方法吗？我知道从全局内存读取和写入很可能是这里的瓶颈,特别是因为我正在尝试获取全局内存的(至少只有一小部分)同步访问.但也许有更好的方法来做到这一点,也许使用内核分解.请注意,我尝试避免在内核期间将数据从GPU读回到CPU(以避免OpenCL命令队列刷新,这也是我所采用的那样糟糕).

2. 在上面的算法设计中,我该如何实现锁定机制？以下代码会起作用吗？特别是,当硬件在SIMD组中执行工作项"真正并行"时,我会遇到问题,比如Nvidia"warps".在我当前的代码中,工作组的所有项目都会尝试以SIMD方式获取锁定.我应该仅限于第一个工作项吗？并使用障碍使他们在本地保持同步？

   #pragma OPENCL EXTENSION cl_khr_global_int32_base_atomics : enable
   
   __kernel void putInBuckets(__global uint *mutex,
                              __global uint *bucket_start,
                              __global uint *new_index)
   {
       __local bucket_size[NUM_BUCKETS];
       __local bucket[NUM_BUCKETS][LOCAL_MAX_BUCKET_SIZE]; // local "new_index"
   
       while (...)
       {
           // process a couple of elements locally until a local bucket is full
           ...
   
           // "lock"
           while(atomic_xchg(mutex, 1)) {
           }
   
           // "critical section"
           __local …

   Run Code Online (Sandbox Code Playgroud)

我正在探索以下算法:

1. 计数排序
2. 基数排序
3. 铲斗排序

我知道这三个都能够在最佳情况下以线性时间运行,但是我很难理解这些情况何时发生,除了计算排序的情况.

以下是我对计数排序的理解,以及如果可能的话我希望如何回答其他两种算法:

当您希望排序的信息之间没有大的间隙时,计数排序以线性时间运行.例如,1,10 ^ 5和545等将创建一个大型数组并且使用内存和遍历效率不高所以这将是使用计数排序的"更糟糕的情况",因此最好的情况是差距很小.

如果有人能帮我理解线性时间发生时基数和桶排序最佳情况的条件,我将不胜感激.

我完全被一个问题困扰,并希望得到一些指导.我从1到8的集合中挑选8个数字的随机集合(例如,5,6,8,1,3,4,2,7)并尝试根据顺序将这些数字作为连续数字的子集他们出现了.

对于上面的示例,第一个桶将以5开始,然后将添加6.点击8时,将启动一个新的桶.每当我们找到属于现有存储桶的数字时(例如,当我们到达时2,它可以添加到1存储桶中),我们将其添加到那里.在这个例子中,在我们到达的所有8个数字之后:

5,6,7
8
1,2
3,4

总共4个水桶.

我实际上并不关心桶的内容,我只想计算给定的8位数字随机数的桶数.我计划循环遍历这些8位数序列中的1000个.

我正在尝试实现美式桶排序。维基百科说：“首先计算每个垃圾箱中掉落的物体数量，然后将每个物体放入其桶中。”

第二阶段，将对象放入适当的桶中时，是否需要使用辅助数组？有没有办法通过在线性时间内交换数组元素来做到这一点？

在下面的代码中,我正在对Bucket Sort的实现进行基准测试.

该bucketsort函数使用结果_bucketsort但将其展平为单个列表.令我惊讶的是,这个过程(Map.toList)需要花费很多时间.

module Main where
import System.Random
import Criterion.Main
import qualified Data.List as List
import qualified Data.Map as Map
import Data.Maybe

insert :: (Ord a) => a -> [a] -> [a]
insert x [] = [x]
insert x (y:xs)
    | x <= y    = x:y:xs
    | otherwise = y : insert x xs

bucketsort :: (Integral a) => [a] -> [a]
bucketsort xs = List.concatMap (snd) . Map.toList $ _bucketsort xs Map.empty

_bucketsort …

我想探讨一下我对桶排序的分析，如下所示。
\n桶排序的实现方式有很多种。其中一些如下。
\n类型 1:
\nif\xc2\xa0we\xc2\xa0know\xc2\xa0the\xc2\xa0range\xc2\xa0of\xc2\xa0our\xc2\xa0elements\xc2\xa0to\xc2\xa0be\xc2\xa0sorted,\xc2 \xa0we\xc2\xa0can\xc2\xa0set\xc2\xa0up\nbuckets\xc2\xa0for\xc2\xa0each\xc2\xa0possible\xc2\xa0element,\xc2\xa0and\xc2\xa0just\xc2\xa0toss\xc2\xa0elements\ xc2\xa0进入\xc2\xa0其\xc2\xa0对应的\xc2\xa0buckets。\xc2\xa0我们\xc2\xa0然后\n清空\xc2\xa0的\xc2\xa0buckets\xc2\xa0in\xc2\xa0order,\xc2\xa0and\xc2\ xa0the\xc2\xa0result\xc2\xa0is\xc2\xa0a\xc2\xa0sorted\xc2\xa0list.\n在\xc2\xa0实现\xc2\xa0这个\xc2\xa0算法，\xc2\xa0we\xc2\xa0can\xc2\xa0easily\ xc2\xa0use\xc2\xa0an\xc2\xa0array\xc2\xa0to\xc2\xa0代表\xc2\xa0our\xc2\xa0buckets,\xc2\xa0where\xc2\xa0the\xc2\xa0value\xc2\xa0at\neach\xc2\xa0array \xc2\xa0index\xc2\xa0将\xc2\xa0表示\xc2\xa0\xc2\xa0的编号\xc2\xa0的\xc2\xa0elements\xc2\xa0in\xc2\xa0\xc2\xa0对应的\xc2\xa0桶。\xc2\xa0If\ xc2\xa0we\xc2\xa0have\xc2\xa0integers\non\xc2\xa0the\xc2\xa0range [0..max],\xc2\xa0then\xc2\xa0we\xc2\xa0set\xc2\xa0up\xc2\xa0an\xc2 \xa0array\xc2\xa0of\xc2\xa0(max + 1)\xc2\xa0integers\xc2\xa0and\xc2\xa0初始化\xc2\xa0all\xc2\xa0the\xc2\xa0values\xc2\xa0to\nzero。\xc2\xa0We \xc2\xa0然后\xc2\xa0继续\xc2\xa0顺序\xc2\xa0到\xc2\xa0the\xc2\xa0unsorted\xc2\xa0array,\xc2\xa0reading\xc2\xa0the\xc2\xa0value\xc2\xa0of\xc2\xa0each\ xc2\xa0element,\xc2\xa0going\n到\xc2\xa0的\xc2\xa0对应的\xc2\xa0index\xc2\xa0in\xc2\xa0the\xc2\xa0buckets\xc2\xa0array,\xc2\xa0和\xc2\xa0递增\xc2\ xa0\xc2\xa0值\xc2\xa0那里。

时间：O(N)
\n空间：O(1)
\n类型2：

示例：按年龄对人员数组进行排序
\n年龄与用于排序的任意整数有些不同。因此它的范围很小[0-150]（所有人的年龄都在0到150之间）。因此，最快的排序方法是分配 151 个链表（我们称之为桶），并根据每个人的年龄将每个人的数据结构放入桶中：

时间：O(N+K)
\n空间：O(N+K)\n

类型 3（维基百科中所示的类型 2 的变体）

函数nextSort是一个排序函数，用于对每个桶进行排序。如果使用插入排序，那么最坏的时间复杂度为 O(n^2)，或者使用合并排序，这样我就可以保持 O(nlgn) 的稳定性。

\n
• 问题：
  \n1>如何被认为是线性排序，是因为类型1还是类型2？
  \n2>如果我像WIkepedia一样使用Type 3，哪种排序可以有效地对每个桶进行排序？
  \n我知道在实践中使用插入排序的原因是我们期望桶很小，对于小列表，插入排序比其他任何方法都快得多。即使在实现合并排序或快速排序时，当列表变得足够小时（例如低于 20 个项目左右），也会使用插入排序。
  \n3>对于类型 3，我可以根据什么来决定存储桶的范围？
  \n这很重要，因为如果您尝试使用大量存储桶（例如远大于 n）进行存储桶排序，则运行时可能主要取决于扫描所有存储桶以查找您实际使用的存储桶所需的时间，即使其中大部分都是空的。
\n

我根据以下内容进行了分析：
\n维基百科
\n桶排序的复杂度怎么可能是 O(n+k)？
\n算法的设计与分析\n1996 年 1 月 23 日讲义
\n http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
\n http://cs.nyu.edu/courses/fall02 /V22.0310-002/lectures/lecture-23.html
\n如果我们使用链表实现桶，那么桶排序的复杂度是 …

首先，大多数声称实现了 的地方bucket sort实际上都在实现counting sort。我的问题是关于Geek Viewpoint和Wikipediabucket sort上的实现。我不太了解/喜欢 Geek Viewpoint 上的哈希函数，也不太了解 Wikipedia 上的哈希函数。有人可以解释一种更简单的方法来为桶排序创建良好的哈希函数吗？普通人可以理解和记住的东西。

什么时候桶排序算法是用于排序的最佳方法？是否有基于数据结构的大小,类型使用它们的推荐指南？

桶排序是一种线性时间排序。

为什么我们要用插入排序呢？我们知道插入排序需要 O(n2) 时间。为什么我们不能在其中使用任何线性排序？正如我们所看到的，在每个桶中我们使用插入排序 O(n2)。桶排序的总复杂度是O(n)吗？为什么我们不使用 O(nlogn) 排序，例如合并排序或快速排序？