问题标签 [radix]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
83 浏览

arrays - 基数排序(为什么我得到 ArrayIndexOutOfBoundsException 行:43)

我已经给这个算法时间,但仍然无法弄清楚我在哪里做错了什么。任何人都可以帮助我解决“基数排序”的逻辑,如果我使用以下代码做得正确,那么请帮助我弄清楚为什么我会在 line:arr[sortedIndex] = tempArray[j][k]; 处得到 ArrayIndexOutOfBoundsException;

0 投票
2 回答
895 浏览

c++ - 使用双向链表的 C++ 基数排序

我正在开发一个程序来使用基数排序对数字列表进行排序,但我一直陷入我认为是无限循环的困境。我认为它要么是我的主要排序功能,要么是我的计数功能。关于我做错了什么的任何想法?

0 投票
0 回答
402 浏览

c++ - 字符串数组的基数排序行为不正确?

我非常接近让这个程序工作,但我试图让这个程序使用基数排序按字母顺序排列一组字符串,并且在弄清楚如何

第一次迭代效果很好,并按第一个字符对所有字符串进行排序。但是,第二次迭代将所有这些都抛到了窗外,并按第二个字符对它们进行排序。如何解决此问题以使其正常工作?

0 投票
3 回答
555 浏览

c - 将十六进制数解释为十进制

我有一个运行 C 代码的嵌入式系统,它的工作非常简单;它通过串行连接读取字符,将接收到的字符解释为十六进制数字,并根据接收到的内容,继续执行其他操作。但是,有一种非常特殊的情况,接收到的字符是十进制而不是十六进制。由于这种情况非常罕见(一种错误情况的错误情况),我不希望修改实际的字符接收来决定是否将接收到的值解释为 dec 或 hex,而是添加一个快速算法到我将数字更改为十进制的情况处理。

你会说什么是最快的(如在最有效的处理器方面)这样做的方式?由于该软件在小型 MCU 上运行,因此任何 C 库函数都不是一个选项,因为我不希望添加更多不必要的#include,因此我正在寻找纯数学算法。

为了清楚起见,我不是在问最快的方法来进行基本的十六进制到十进制转换,如 0x45 -> dec 69,但我想做的是转换例如。0x120 转化为十进制 120。

提前致谢!

编辑:对不起,我会尝试更详细地解释。实际代码太长了,我认为没有必要在这里粘贴。所以这就是发生的事情:

首先,我从串行线上读取接收到的数字,比如说“25”。然后我把它变成十六进制数,所以我有一个带有读取值的变量,比如说 X = 0x25。这已经很好了,我不想对此进行修改。在这种非常特殊的情况下,我现在想做的只是改变变量的解释,而不是 X == 0x25,X==25。十六进制的 0x25 变成十进制的 25。这种变化必须有某种数学公式,而不需要任何特定于处理器的指令或库函数?

0 投票
2 回答
1823 浏览

c - C中基数排序的不同基础

我很难理解基数排序。我在实现代码以使用 2 或 10 的基数时没有问题。但是,我有一个需要命令行参数来指定基数的分配。基数可以是 2 - 100,000 之间的任何值。我花了大约 10 个小时试图理解这个问题。我不要求直接回答,因为这是家庭作业。但是,如果有人可以对此有所了解,请这样做。

有几件事我不明白。基数为 100,000 有什么意义?那怎么行。我知道字母表中的每个字母或每个数字 1-9 都有一个基数。我似乎无法理解这个概念。

如果我不够具体,我很抱歉。

0 投票
2 回答
4653 浏览

performance - 基数排序的最佳基础

我已经阅读了关于这个主题的几个来源。但是,我很难弄清楚这些公式的确切含义。当 b = n 时,基数排序似乎是线性的。这是否意味着,我应该将基数设置为数组的长度?

如果我有一个 1 亿个整数的数组,范围从 0 到 10 亿,我应该选择基数 1 亿?

如果这不正确,请尝试为我简化它。我能找到的大多数基数排序示例只有以 10 为底或以 2 为底,因此它们对于分别大于 10 或 2 的数组来说很慢,或者我就是不明白。

谢谢你的帮助。

0 投票
1 回答
583 浏览

hex - 十六进制的基数

Pierre Terdiman 在他的文章“Radix Sort Revisited”中告诉我们:

例如,您需要 4 次通过才能对标准 32 位整数进行排序,因为在十六进制中,基数是一个字节。

但是 0xAB 有两个基数,即 A 和 B,都是 4 位宽。

那么,十六进制的基数是什么?因为看不懂文章。

0 投票
1 回答
126 浏览

.net - 什么样的内存基数、列表、B-Tree 或其他布局适合 IPv6 阻止列表?(uint128)?

我需要为 IPv6 创建白名单/阻止名单。

在 IPv6 中,有哪些内存选项可用于在每个主机或每个网络的基础上维护信息?

我目前HashTable<UInt32>为 IPv4 使用 a,但从未真正掌握子网跟踪、CIDR 等。IPv6 有许多不同的方式来表示 IP 范围,这使我将 IP 组合在一起并解释它们的工作变得复杂。

话虽如此..拥有这样一个阻止列表/白名单的最有效方式(搜索速度或内存紧凑性)是什么?

TL;DR 问题

  • 如何查找 aUInt128是否在列表/btree/哈希表中?哪种数据结构适合这个?

  • 如何找到彼此“接近”的 IP。这通常称为 CIDR,但我们也可以将其表示为 BigInt 的值比较。

我刚刚想到的一种方法是加密累加器的工作原理。也许有一种方法可以利用累加器的“成员资格”能力来确定一个数字是否是集合的成员

0 投票
1 回答
141 浏览

c++ - 从不同的基数转换后查找位数的方法

引号中的文字为我的程序提供了一些背景知识,以防需要理解我的问题,如果您不想阅读它,您可能能够完全理解末尾未引用的内容。

我正在研究 C++ 中排序的常见项目,我目前正在做基数排序。我把它作为一个函数,接受一个字符串向量、一个包含最大位数的整数和一个带有数字基数/基数的整数:(numbers, maxDigits, radix)

由于该程序接受不同基数的数字并作为字符串,因此我使用 stoi 将它们转换为以 10 为基数的整数,以使该过程更易于概括。以下是该算法的快速摘要:

  • 创建 10 个队列来保存值 0 到 9
  • 遍历每个数字(maxDigit 次)
    • 遍历向量中的每个数字(这里它转换为以 10 为底)
    • 根据它正在查看的当前数字将它们放入队列
    • 将数字从队列中从头到尾拉回向量中

至于我试图解决的问题,我想在将 maxDigit 值(用户输入的任何基数)转换为基数 10 后将其更改为 maxDigit 值。换句话说,假设用户使用了代码

对最大位数为 8 且基数为 2 的数字向量进行排序。由于我将数字的基数转换为 10,因此我正在尝试找到一种算法来更改 maxDigits,如果这有意义的话。

我已经尝试过这么多的思考,试图通过反复试验找出一种简单的方法。如果我能在正确的方向上获得一些提示或帮助,那将是一个很大的帮助。

0 投票
1 回答
1319 浏览

c - 如何在C中找到一棵树的高度

我在编写算法来查找特里树的高度时遇到了麻烦。我不知道如何开始或如何做。抱歉,如果这是一个“菜鸟”问题,但我对尝试很陌生,这是我作业中唯一缺少的部分。

无论如何,这里是特里树的结构:

所以基本上,如果'a'是一个孩子,那么在chidren[0]中会有一个Trie,如果'b'不是孩子,children[1]将为NULL。如您所见,字符由链接索引隐式定义,如果过去节点的字符在当前节点之前形成一个单词,则“Boolean IsItAWord”将为真。

你们能给我一点启示吗?我唯一知道的是,高度可以由最长单词的长度 + 1 来定义。但我不知道该怎么做。我真的只是想要一个解决方案,所以任何找到这个 trie 高度的方法都将不胜感激。

谢谢你。