1回答
在我的日常工作中，我经常处理包含数百万行的数据集，有时是上亿行，有时超过10亿行。这些数据集通常需要排序。键几乎总是大整数值(通常是9位数)。有时数据集具有9位和3位的组合键。
我想知道是否有可能在SAS中实现(LSD-first)基数排序宏，它可以用来代替PROC SORT来减少对这些数据集进行排序所花费的时间。我已经调整了排序，在适当的地方使用压缩，只保留相关的字段(或使用tagsort)，适当地调整字段长度，不进行不必要的排序等等。
我使用的硬件有局限性--让我们假设我只有2G的内存可供SAS使用，因此解决方案不需要将临时数组中的所有键值都放入内存中(至少不是一次全部放入)。
该解决方案
浏览 1提问于2011-12-23得票数 2
回答已采纳
1回答
计数排序的稳定性
、、
我用python实现了一个计数排序算法。我看到计数排序是稳定的，因为它保留了元素在原始数组中的顺序。你认为下面的实现是稳定的吗？
def countingsort(A,n):
C = [0]*n
B = [0]*n
# the value of A[i] becomes the index for counting
# C now stores the no. of occurences of element A[i] in A
for i in A:
C[i] = C[i] + 1
浏览 4提问于2015-10-22得票数 1
这是一个家庭作业problem.So，我寻找的是提示而不是解决方案。考虑一组n个数字。每个数字都是'k‘位长。假设'k‘要大得多，不适合记忆中的任何一个单词。在这种情况下，合并排序和基数排序的复杂度是多少？
我的分析是-渐近复杂性不依赖于底层架构细节，如数字占用的字数等。可能是恒定因素变化和算法运行较慢，但总体复杂性保持不变。例如，在像Python这样处理任意长度整数的语言中，算法保持不变。但我的一些朋友认为，随着数字“w”所占单词的数量越来越多，复杂性确实会发生变化。
我走的路对吗？
浏览 1提问于2014-09-18得票数 2
既然所有比较排序算法至少需要n lg n时间，当我们可以将快速排序列表中的项表示为位并使用基数排序之类的线性排序时，为什么我们需要使用像快速排序这样的东西呢？
浏览 0提问于2014-10-01得票数 0
我听说基数排序的最坏内存情况是O(n+r)，其中n是数组大小，r是基数。但是，由于在计算中很少使用超过16进制的任何东西，那么在实践中，无论是r=2还是r=100真的很重要吗？对太空有什么真正的影响吗？
浏览 18提问于2020-09-23得票数 0
回答已采纳
我在一次面试中被问到了这个问题。我不能比O(NlogN)做得更好。我每次都在排序。
浏览 0提问于2018-05-23得票数 0
我知道32位整数被分解成8位的块。有人能给我解释一下通行证是如何工作的吗？一个简单的例子将帮助我更好地理解它。例如，我有2147507648和2147507672。我将它们分解为8位块。128093216是2147507672年度的分项数字，128093192是2147507648年度的分项数字。
我理解LSD基数排序是如何对基数10进行排序的。如果有人能在我得到8位块之后向我展示如何对这32位整数进行排序，我将不胜感激。
非常感谢!
浏览 2提问于2013-10-16得票数 0
我实现了一个使用排序的算法。我尝试过Thrust::sort_by_key，对一个包含10^7个元素的数组进行排序大约需要0.4秒。
我认为bitonic排序网络应该比Thrust::sort_by_key更快。然而，bitonic排序需要大约2.5秒才能对上面提到的相同数组进行排序。我使用了SDK提供的bitonic排序网络。我只是稍微修改了一下原来的bitonic排序。
你能告诉我为什么吗？或者给我一些建议？
谢谢,
易克
2011年8月15日
浏览 2提问于2011-08-15得票数 1
回答已采纳
1回答
事情是这样的。我在做leetcode 164的最大间隔。这个问题的最佳解决方案是存储桶排序。
这让我对排序问题有了更多的思考。假设我们有一个列表，如下：
2 ,5 ,19,444，-14，89，16，77
我认为，我们可以将这些数字按两个不同的范围排列，( min，mid) ( mid，max)，而mid应该是min+ (max - min) / 2；
因此我们得到(-14,215) (216,444)
我们将min设置为最左边，max设置为最右边，并根据范围填充其他元素，然后我们得到
-14 2、5、19、89、16、77
444
我们回想一下两个范围的排序，对于左边的一个，我们有(-14，
浏览 5提问于2019-10-19得票数 0
我在推力中使用sort和unique by key函数。我只是想知道在推力中排序函数的步长复杂度是多少，唯一的按键排序函数的功和步长复杂度是什么。
根据我的知识，我认为排序的工作复杂度是O(NlogN)。但是我不知道unique_by_key操作是什么
浏览 1提问于2012-04-03得票数 1
2回答
我已经研究了基数排序算法的最佳、平均和最坏情况时间。
平均值为N×K/D
我知道K是钥匙/桶的数量
有人知道D代表什么吗？
参考-
浏览 4提问于2013-03-13得票数 0
3回答
基数是如何对浮点数据进行排序的？例如12.4，45.13等等，它会先读取小数点的右边吗?还是先读取小数点的左边?然后如果它读取小数点的右边，它将如何处理数字，它会先读取最右边的数字吗？
浏览 0提问于2011-01-16得票数 3
3回答
按所有元素对元组数组进行排序
、、、、
我想按所有元素对元组数组进行排序(就像它们在trie中一样)。如果输入是(1,2,5)，(1,2,3)，(1,1,4)，(2,8,9)，相应的输出将是(1,1,4)，(1,2,3)，(1,2,5)，(2,8,9)。相应的trie将是：
root
/ \
1 2
/ \ |
1 2 8
| /\ |
4 3 5 9
我在考虑对元组中的每个位置使用搜索树。还有一种明显的幼稚方式(按第一个位置排序，然后按第二个位置排序，等等)。有没有人看到更好的方法？
浏览 4提问于2013-03-19得票数 2
回答已采纳
1回答
在区间n整数中有[0,n^c]整数，其中c是正整数。
我可以用哪种算法在线性时间对这些整数进行排序？
我确实看过RadixSort的问题如下:给定最长的数字最多有c_nlogn位数，那么RadixSort不会在O(n_logn)时间内运行吗？
浏览 1提问于2017-06-10得票数 0
回答已采纳
2回答
我有一个包含uint32_t类型的结构数组。知道数组的最大值和最小值后，我想实现计数排序或基数排序，根据uint32_t对数组进行排序，值的范围可能会很大。我不知道如何对结构数组而不是整数数组进行排序。或者，有没有更好的排序算法？谢谢!
浏览 5提问于2015-05-09得票数 2
2回答
我有n个介于0和(n^4 - 1)之间的数字，最快的排序方法是什么？
当然，nlogn是微不足道的，但我考虑了基数n的基数排序选项，然后它将是线性时间，但我不确定，因为-1。
感谢您的帮助！
浏览 1提问于2015-09-01得票数 0
1回答
文件C#中的基数排序
、、、
我必须以两种方式对汽车牌照(ABC 123)进行基数排序: 1)数组2)链表。最有趣的是排序必须在文件中完成。例如，从现在开始，我们将只讨论数组。我生成车号并将其放入数组中，然后使用二进制写入将所有生成的汽车车牌写入该文件。之后，我将新生成的文件交给Radix Sort，他需要进行魔术操作。我将展示我目前的代码，但它实际上不是‘真正的’基数排序，因为我的大脑无法理解如何在文件中实现基数排序。(我已经实现了普通数组和链表的基数排序，但是当它在一个文件中完成时，它是令人兴奋的)。我只是想问你们是否有任何关于我如何改进排序算法的提示或想法，因为它非常慢。谢谢。
PROGRAM.CS
public s
浏览 5提问于2020-04-05得票数 2
1回答
我一直在研究各种排序算法，有一种称为基数排序的算法，在这种算法中，我必须以2^(lg )为基数对数字进行排序，但我不知道这是什么。我的意思是，我知道基数2是二进制的，但是有了log n，我就不太明白了。
所以我想知道基数2^(lg )实际上是什么，以及它会以什么方式影响我的代码。
浏览 0提问于2020-05-07得票数 1
1回答
好的，我必须为无符号整数和浮点数创建一个基数排序。我的无符号整数版本可以正常工作，但我在处理浮点值时遇到了一些问题。基本上，它按照浮点数的整数值对数组的值进行排序，但不会基于小数值对其进行排序。(例如36.65234将出现在36.02311之前，如果它出现在未排序的数组中)这段代码是我进行位操作和掩码的地方，我非常确定这就是我的问题所在。
/* For loop to create bin */
for(int i=0; i<n; i++){
temp_int = (((unsigned int)(list[i]))>>bitwise)&0xff;
b
浏览 0提问于2011-03-01得票数 5
回答已采纳
1回答
测量基数排序时的奇怪结果
、、、、
我正在使用timeit模块测量基数和计数排序的执行时间。我使用的是位于<0；1000000>区间上的100组随机整数。集合中的所有整数都是唯一的。第一组由10000个整数组成，最后一组包含1000000个整数。每组排序10次，记录平均时间(作为full time/10)。在基排序的日志文件中有一些奇怪的结果，我不确定这是timeit模块的问题还是我的排序算法的问题：
基排序日志
integers count, average time
......,.............
760000,1.51444417528
770000,1.31519716697
780000,1.33
浏览 2提问于2014-12-28得票数 0
1回答
O(n)中的2键搜索算法
、、、
我必须找到一个算法来对一个复杂度为O(n)的数组进行排序。该数组的长度为n，具有两个不同的键。
例如，java中的数组：
int[][] array = {{1,2},{2,1},{1,1}};
结果应该是
1 1
1 2
2 1
我在努力解决这个问题..
谁能帮我呢？
提前感谢
浏览 2提问于2013-03-19得票数 0
回答已采纳
2回答
我有一个给定的日期字符串数组，格式是dd/mm/yyyy。
我想用基数排序按月和年排序，但我不知道如何排序，因为最终它将根据月份的最大数目进行排序。
例如，我有以下数组: 16/04/2012 01/05/2013 01/02/2012 10/11/2012 01/12/2012
通常排序后的结果是: 01/02/2012 16/04/2012 01/05/2013 10/11/2012 01/12/2012
而我想要的是: 01/02/2012 16/04/2012 10/11/2012 01/12/2012 01/05/2013
我还没有编写代码，因为我不知道算法是如何工作的，我只能用生成
浏览 11提问于2012-05-02得票数 0
回答已采纳
2回答
假设我有一个数字列表，并且对于每个数字n，我知道n是由一些恒定的位数表示的。
即使我的数字是实数而不一定是整数，我也可以使用基数排序吗？
浏览 0提问于2016-04-07得票数 1
2回答
理解C中的基类
、、、
我正在使用这个作为参考，看看算法是如何实现的。除本部分外，我大部分理解：
/*
* update all the buckets. If bucket[8] has 2,
* then there are 2 elements present till bucket 8
*/
for (i = 1; i < 10; i++)
bucket[i] = bucket[i] + bucket[i-1];
我不明白作者在那个循环中做了什么。有人能解释一下发生了什么事吗？
是的，我正在用纸和笔来观察到底发生了什么。我只是想澄清一下
浏览 2提问于2013-09-18得票数 0
回答已采纳
在c++语言中，为了获得O(n+m)的最佳时间复杂度，将两个未排序的数组排序到一个排序的数组中。我们如何修改这段代码，使其时间复杂度为O(m+n)？两个数组的大小应该不同。这里的时间复杂度为O((m+n)log(m+n))。如何使其复杂度达到O(m+n)？
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
浏览 0提问于2020-06-24得票数 0
假设我写了一个非常棒的接口。事实上，我想要一些我用来实现它们的内置类型，这样我写的任何使用这个接口的代码也可以使用内置类型。
public interface IKickAss
{
int Yeahhhhhhh() { get; }
}
public static class Woot
{
public int Bar(IKickAss a, IKickAss b)
{
return a.Yeahhhhhhh - b.Yeahhhhhhh;
}
}
// What I'd like to do, sort of.
public par
浏览 0提问于2009-04-29得票数 3
与基于比较的排序算法相比，我是关于基数排序效率的，在这里我发现了以下内容：
例如，考虑自下而上的合并排序。第一次传递将比较随机键对，但最后一次传递将比较排序顺序非常接近的键。这使得合并排序在这类输入上花费了O(n (log )2)时间。
有人能帮我理解O(n (log n)2)部分吗？
浏览 4提问于2016-03-13得票数 0
回答已采纳
2回答
我正在尝试用C语言使用POSIX线程来并行化基数排序。特殊之处在于需要为浮点数实现基数排序。目前，代码是按顺序运行的，但我不知道如何将代码并行化。有人能帮我吗？任何帮助都是非常感谢的。
浏览 6提问于2021-08-05得票数 0
我知道如何使用基数排序来对整数进行排序。
但是如何使用它对字符串进行排序呢？或者是浮点数？
浏览 1提问于2012-03-10得票数 4
回答已采纳
2回答
我想知道是对整数值使用基数排序更有效，还是先将值转换为二进制值再进行排序。
谁能给我解释一下使用基数排序和二进制数排序而不是只使用整数排序的优缺点？
例如，我想对5个值进行排序。(170，2，19，40,100)
使用基数排序，Pro's和Con's使用他们的二进制表示是什么？(010101010,0010,010011,0101000,01100100)
浏览 9提问于2015-12-22得票数 0
我得到了一个整数数组，它们不一定是排序的。我必须找到一对nos，与数组中任何一对nos相比，它们之间的差异最小。时间效率应为O(n)。
浏览 0提问于2011-02-14得票数 2
在评估问题的复杂性时，我总是遇到问题。我通常尝试寻找O(n)解，但有时O(nlogn)甚至O(n^2)是最好的。
我知道的一个“经验法则”是，如果你有一个排序的数组，你需要找到一些东西，它可能可以在O(logn)中完成。我也知道排序不可能比O(nlogn)更快。没有经验的程序员有没有类似的规则可以遵循？你知道重复出现的问题有多复杂吗？
对我来说，最麻烦的是O(n^2)，特别是当我面临考试压力，浪费时间去寻找更好的考试时。
我希望这不是一个过于宽泛和基于观点的问题。
谢谢!
浏览 0提问于2014-03-02得票数 0
1回答
我终于实现了基于十进制的基数排序，但我想将其转换为按位排序。
void LSD_radixSort (unsigned int * A, int size, int r)
{
// Find the maximum number to know number of digits
int m = getMax(A, size);
// Do counting sort for every digit. Note that instead of passing digit
// number, exp is passed. exp is 10^i wher
浏览 1提问于2014-03-20得票数 0
1回答
要排序的数组大约有一百万个字符串，其中每个字符串的长度最多可达一百万个字符。
我正在寻找GPU排序算法的任何实现。
我有一个大小约为1MB的数据块，我需要构造。现在，您可以看到在非常小的内存中拥有一百万个字符串是如何可能的。
浏览 0提问于2010-07-15得票数 7
回答已采纳
考虑两个k位数(以二进制表示)：
$$A = A_1 A_2 A_3 A_4 ... A_k $$
$$B = B_1 B_2 B_3 B_4 ... B_k $$
为了进行比较，我们从左到右扫描，查找0的出现，如果该数字也是0 (对于两个数字)，则检查相反的数字，注意如果发现这样的情况，则0的源小于1的源。但是如果数字是：
111111111111
111111111110
显然，这将需要扫描整个数字，如果我们事先没有被告知任何关于数字的信息，然后简单地给出它们：
比较需要$O(k)$时间。
因此，当我们查看排序方法的代码时，例如高性能的快速排序：
HPQuicksort(list): T
浏览 0提问于2014-02-14得票数 1
2回答
也许我说得有点不清楚：
我想要做的是尽可能快地对多个向量进行排序。例如，我有200个向量，其中有200个双精度向量。
浏览 1提问于2013-09-27得票数 0
推力函数可以使用多个GPU进行计算吗？我已经写了这个推力代码，它在单个GPU上工作得很好。(特斯拉C2050)但我有另外三个特斯拉C2050卡连接到机器上，我想用它们来进行我的计算。
我知道，通过将多个GPU连接到一台机器上，我可以在每个GPU上并行运行一个CUDA内核，例如，在设备0上运行内核0，在设备1上运行内核1，等等。但在我的例子中，我想在一个单一的推力函数调用上使用所有4个GPU，比如推力：：排序。这个是可能的吗？
浏览 2提问于2012-02-04得票数 2
1回答
我写了一个简单的程序，按O(n)排序。它的内存效率非常低，但这不是重点。
它使用HashMap背后的原理进行排序：
public class NLogNBreak {
public static class LinkedListBack {
public LinkedListBack(int val){
first = new Node();
first.val = val;
}
public Node first = null;
public void insert(int
浏览 0提问于2011-08-23得票数 28
回答已采纳
我正在尝试理解在基数排序中使用不稳定的排序算法(如快速排序)的危险。另外，在这两种情况下(即MSD基数排序和LSD基数排序)都必须使用稳定的算法吗？
提前谢谢。
浏览 38提问于2016-07-28得票数 2
回答已采纳
1回答
我有一个关于基数排序实现的问题。对于二进制的16位二进制补码数，基数排序是如何工作的？我不完全确定如何构造一个实现(可能是因为我在做二的补码转换时遇到了困难……)。有没有人有什么解释或者教程？
在进阶时谢谢！
浏览 1提问于2011-12-07得票数 0
回答已采纳
1回答
我有一个MST图的源数组和目标数组，通过将它们的MST I放在实际顶点的位置来创建，如下所示：
资源中心: 16 16 16 9 9 9 19 19 19 10 10 10 16 16 16 9 9 9 19 19 19
目标9 9 10 9 22 10 10 16 16 16 10 10 16 19 10 10 13 9 10 13 14 19 19 19 9 22 29 9 9 19 16 16 16 9 10 10 9 9 16 34
这些源与其在数组中的目的地相对应地排列。我想把相似的配对带到一个地方。例如，我的o/p应该是这样的..
src 16 16 16 9 9 9
目标9 9
浏览 0提问于2013-03-22得票数 0
假设图G的边权在[0，1]上均匀分布，.Which算法素数或Kruskals算法会更快吗？我认为这将是kruskals，因为我们可以利用特定的排序算法，因为排序是kruskals算法中的瓶颈步骤。
浏览 0提问于2013-06-10得票数 1
1回答
我正在尝试使用中的就地基数排序示例。到目前为止，我有这样的想法：
import std.random;
void swap(ref string i,ref string j) {
string tmp = i;
i = j;
j = tmp;
}
void radixSort(ref string[] seqs, size_t base = 0) {
if(seqs.length == 0)
return;
size_t TPos = seqs.length, APos = 0;
size_t i = 0;
while(i
浏览 0提问于2011-01-25得票数 6
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
