-
Radix
2018-07-17 16:41:591010 Radix (25)(25 分) Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is "yes", if 6 is a decimal number and 110 is a binary ...1010 Radix (25)(25 分)
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is "yes", if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:\ N1 N2 tag radix\ Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number "radix" is the radix of N1 if "tag" is 1, or of N2 if "tag" is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print "Impossible". If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible
题目大意:给定两个数,并给出其中一个的基数,求另一个数以什么为基数可以等于这个数,如果有输出最小值,否则,输出impossible;
代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long string a,b,c; ll s,sc; int trans(char c) { int a; if(c>='0'&&c<='9') a=c-'0'; if(c>='a'&&c<='z') a=c-'a'+10; return a; } ll binary(ll low,ll high) { while(low<high) { ll mid=(low+high)/2; sc=0; for(int j=c.size()-1,x=1;j>=0;j--,x*=mid) { sc+=trans(c[j])*x; if(sc>s) break; } if(sc==s) return mid; else if(sc>s) high=mid-1; else low=mid+1; } return 0; } int main() { int tag,radix; ll flag=0; s=0; cin>>a>>b>>tag>>radix; if(tag==1) { c=b; for(int i=a.size()-1,x=1;i>=0;i--,x*=radix) s+=trans(a[i])*x; } else { c=a; for(int i=b.size()-1,x=1;i>=0;i--,x*=radix) s+=trans(b[i])*x; } radix=0; for(int i=0;i<c.size();i++) radix=max(radix,trans(c[i])); for(int i=radix+1;i<=100;i++) { sc=0; for(int j=c.size()-1,x=1;j>=0;j--,x*=i) sc+=trans(c[j])*x; if(s==sc) { flag=i; break; } if(i==100) { flag=binary(100,s+1); } } if(flag!=0) cout<<flag<<endl; else cout<<"Impossible"<<endl; return 0; }
-
Radix4Radix2FFT实现
2019-08-12 04:38:11Radix-4/Radix-2 FFT 实现 -
radix:Crystal的Radix树实现-源码
2021-02-05 07:14:54radix:Crystal的Radix树实现 -
radix-operator:Radix平台的运算符-源码
2021-01-30 06:53:22使用Github操作构建radix-operator和radix-pipeline ,然后每当将新映像推送到相应分支的容器注册表时,使用将radix-operator部署为通过Helm发布进行群集。 定义了可以推送到radixdev和radixprod的操作的。 这些是... -
Radix Sort
2021-01-08 14:09:25<div><p>Radix Sort algorithm: https://en.wikipedia.org/wiki/Radix_sort</p> <p>The code coverage will probably drop a little, but I don't know how to avoid this since the untested part of my code ... -
Missing radix parameter radix 解决办法
2019-11-18 14:41:25Missing radix parameter radix 按照下面的文档格式,添加radix参数即可Missing radix parameter radix
按照下面的文档格式,添加radix参数即可
-
Radix TRee
2018-11-12 17:43:19Radix TRee分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow
也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!
http://s.sousb.com/2011/04/19/%E7%BB%B4%E6%8A%A4100%E4%BA%BF%E4%B8%AAurl/
题目:url地址 比如http://www.baidu.com/s?wd=baidu 的属性,包括定长属性(比如其被系统发现的时间)和不定长属性(比如其描述)实现一个系统a.储存和维护100亿个url及其属性。b.实现url及其属性的增删改。c.查一个url是否在系统中并给出信息。d.快速选出一个站点下所有url
提示:因为数据量大,可能存储在多台计算机中。
分析:这是一道百度的笔试题,这道题比较难,笔者只能给出几个认识到的点。
- 首先,这些url要经过partition分到X台机器中:考虑使用一个hash函数hash(hostname(url))将url分配到X台机器中,这样做的目的:一是数据的分布式存储,二是同一个站点的所有url保存到同一台机器中。
- 其次,每台机器应该如何组织这些数据?一种思路是用数据库的思路去解决,这里提供另外一种思路。考虑将url直接放在内存,接将url组织成树状结构,对于字符串来说,最长使用的是Trie tree,由于所占空间由最长url决定,在这里绝对不适用,再加上很多url拥有相同的属性(如路径等)这样,使用trie tree 的一个变种radix tree,相比会非常节省空间,并且不会影响效率。
- 最后,给出了存储模型,上面的abcd四问该怎么回答,这里就不一一解答了。
Radix tree
From Wikipedia, the free encyclopedia(Redirected from Patricia trie)In computer science, a radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized triedata structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike in regular tries, edges can be labeled with sequences of elements as well as single elements. This makes them much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes.
As an optimization, edge labels can be stored in constant size by using two pointers to a string (for the first and last elements). [1]
Note that although the examples in this article show strings as sequences of characters, the type of the string elements can be chosen arbitrarily (for example, as a bit or byte of the string representation when using multibyte character encodings or Unicode).
Contents
[hide]Applications[edit]
As mentioned, radix trees are useful for constructing associative arrays with keys that can be expressed as strings. They find particular application in the area of IProuting, where the ability to contain large ranges of values with a few exceptions is particularly suited to the hierarchical organization of IP addresses.[2] They are also used for inverted indexes of text documents in information retrieval.
Operations[edit]
Radix trees support insertion, deletion, and searching operations. Insertion adds a new string to the trie while trying to minimize the amount of data stored. Deletion removes a string from the trie. Searching operations include exact lookup, find predecessor, find successor, and find all strings with a prefix. All of these operations are O(k) where k is the maximum length of all strings in the set. This list may not be exhaustive.
Lookup[edit]
The lookup operation determines if a string exists in a trie. Most operations modify this approach in some way to handle their specific tasks. For instance, the node where a string terminates may be of importance. This operation is similar to tries except that some edges consume multiple elements.
The following pseudo code assumes that these classes exist.
Edge
- Node targetNode
- string label
Node
- Array of Edges edges
- function isLeaf()
function lookup(string x){ // Begin at the root with no elements found Node traverseNode := root; int elementsFound := 0; // Traverse until a leaf is found or it is not possible to continue while (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // Get the next edge to explore based on the elements not yet found in x Edge nextEdge := select edge from traverseNode.edges where edge.label is a prefix of x.suffix(elementsFound) // x.suffix(elementsFound) returns the last (x.length - elementsFound) elements of x // Was an edge found? if (nextEdge != null) { // Set the next node to explore traverseNode := nextEdge.targetNode; // Increment elements found based on the label stored at the edge elementsFound += nextEdge.label.length; } else { // Terminate loop traverseNode := null; } } // A match is found if we arrive at a leaf node and have used up exactly x.length elements return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length);}
Insertion[edit]
To insert a string, we search the tree until we can make no further progress. At this point we either add a new outgoing edge labeled with all remaining elements in the input string, or if there is already an outgoing edge sharing a prefix with the remaining input string, we split it into two edges (the first labeled with the common prefix) and proceed. This splitting step ensures that no node has more children than there are possible string elements.
Several cases of insertion are shown below, though more may exist. Note that r simply represents the root. It is assumed that edges can be labelled with empty strings to terminate strings where necessary and that the root has no incoming edge.
Deletion[edit]
To delete a string x from a tree, we first locate the leaf representing x. Then, assuming x exists, we remove the corresponding leaf node. If the parent of our leaf node has only one other child, then that child's incoming label is appended to the parent's incoming label and the child is removed.
Additional Operations[edit]
- Find all strings with common prefix: Returns an array of strings which begin with the same prefix.
- Find predecessor: Locates the largest string less than a given string, by lexicographic order.
- Find successor: Locates the smallest string greater than a given string, by lexicographic order.
History[edit]
Donald R. Morrison first described what he called "Patricia trees" in 1968;[3] the name comes from the acronym PATRICIA, which stands for "Practical Algorithm To Retrieve Information Coded In Alphanumeric". Gernot Gwehenberger independently invented and described the data structure at about the same time.[4]
Comparison to other data structures[edit]
(In the following comparisons, it is assumed that the keys are of length k and the data structure contains n members.)
Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ logn, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes (in the case where comparisons begin at the start of the string). In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons, and require many fewer nodes.
Radix trees also share the disadvantages of tries, however: as they can only be applied to strings of elements or elements with an efficiently reversible mapping to strings, they lack the full generality of balanced search trees, which apply to any data type with a total ordering. A reversible mapping to strings can be used to produce the required total ordering for balanced search trees, but not the other way around. This can also be problematic if a data type only provides a comparison operation, but not a (de)serialization operation.
Hash tables are commonly said to have expected O(1) insertion and deletion times, but this is only true when considering computation of the hash of the key to be a constant time operation. When hashing the key is taken into account, hash tables have expected O(k) insertion and deletion times, but may take longer in the worst-case depending on how collisions are handled. Radix trees have worst-case O(k) insertion and deletion. The successor/predecessor operations of radix trees are also not implemented by hash tables.
Variants[edit]
A common extension of radix trees uses two colors of nodes, 'black' and 'white'. To check if a given string is stored in the tree, the search starts from the top and follows the edges of the input string until no further progress can be made. If the search-string is consumed and the final node is a black node, the search has failed; if it is white, the search has succeeded. This enables us to add a large range of strings with a common prefix to the tree, using white nodes, then remove a small set of "exceptions" in a space-efficient manner by inserting them using black nodes.
The HAT-trie is a radix tree based cache-conscious data structure that offers efficient string storage and retrieval, and ordered iterations. Performance, with respect to both time and space, is comparable to the cache-conscious hashtable.[5][6] See HAT trie implementation notes at [1]
See also
利用Radix树作为Key-Value 键值对的数据路由
引言:总所周知,NoSQL,Memcached等作为Key—Value 存储的模型的数据路由都采用Hash表来达到目的。如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。
借助于Radix树,我们同样可以达到对于uint32_t 的数据类型的路由。这个灵感就来自于Linux内核的IP路由表的设计。
作为传统的Hash表,我们把接口简化一下,可以抽象为这么几个接口。
12345void
Hash_create(
size_t
Max );
int
Hash_insert( uint32_t hash_value , value_type value ) ;
value_type *Hash_get( uint32_t hashvalue );<br><br>
int
Hash_delete( uint32_t hash_value );
接口的含义如其名,创建一个Hash表,插入,取得,删除。
同样,把这个接口的功能抽象后,利用radix同样可以实现相同的接口方式。
1 int mc_radix_hash_ini(mc_radix_t *t ,int nodenum ); 2 3 int mc_radix_hash_insert( mc_radix_t *t , unsigned int hashvalue , void *data ,size_t size ); 4 5 int mc_radix_hash_del( mc_radix_t *t , unsigned int hashvalue ) ; 6 7 void *mc_radix_hash_get( mc_radix_t *t , unsigned int hashvalue ) ;
那我们简单介绍一下Radix树:
Radix Tree(基树) 其实就差不多是传统的二叉树,只是在寻找方式上,利用比如一个unsigned int 的类型的每一个比特位作为树节点的判断。
可以这样说,比如一个数 1000101010101010010101010010101010 (随便写的)那么按照Radix 树的插入就是在根节点,如果遇到 0 ,就指向左节点,如果遇到1就指向右节点,在插入过程中构造树节点,在删除过程中删除树节点。如果觉得太多的调用Malloc的话,可以采用池化技术,预先分配多个节点,本博文就采用这种方式。
1 typedef struct _node_t 2 { 3 char zo ; // zero or one 4 int used_num ; 5 struct _node_t *parent ; 6 struct _node_t *left ; 7 struct _node_t *right ; 8 void *data ;//for nodes array list finding next empty node 9 int index ;10 }mc_radix_node_t ;
节点的结构定义如上。
zo 可以忽略,父节点,坐指针,右指针顾名思义,data 用于保存数据的指针,index 是作为 node 池的数组的下标。
树的结构定义如下:
1 ypedef struct _radix_t 2 { 3 mc_radix_nodes_array_t * nodes ; 4 mc_radix_node_t * root ; 5 6 mc_slab_t * slab ; 7 8 9 /*10 pthread_mutex_t lock ;11 */12 int magic ;13 int totalnum ;14 size_t pool_nodenum ;15 16 mc_item_queue queue ;17 }mc_radix_t ;
暂且不用看 nodes 的结构,这里只是作为一个node池的指针
root 指针顾名思义是指向根结构,slab 是作为存放数据时候的内存分配器,如果要使用内存管理来减少开销的话(参见slab内存分配器一章)
magic用来判断是否初始化,totalnum 是叶节点个数,poll_nodenum 是节点池内节点的个数。
queue是作为数据项中数据的队列。
我们采用8421编码的宏来作为每一个二进制位的判断:
1234#define U01_MASK 0x80000000
#define U02_MASK 0x40000000
#define U03_MASK 0x20000000
#define U04_MASK 0x10000000<br>.<br>.<br>.<br>.
#define U31_MASK 0x00000002
#define U32_MASK 0x00000001类似这样的方式来对每一位二进制位做判断,还有其他更好的办法,这里只是作为简化和快速。
123456unsigned
int
MASKARRAY[32] = {
U01_MASK,U02_MASK,U03_MASK,U04_MASK,U05_MASK,U06_MASK,U07_MASK,U08_MASK,
-
go-radix, Radix树的Golang实现.zip
2019-09-18 06:58:10go-radix, Radix树的Golang实现 提供实现 radix的radix 包。 包只提供单个 Tree 实现,针对稀疏节点优化。作为一个基数树,它提供以下内容:O(k) 操作。在许多情况下,这可以能比散列表快,因为哈希函数是 O(k) 操作... -
Other radix
2020-12-25 18:55:55<div><p>POSIX C also offers Radix 64 <p>although a different implementation might be better, as <p><code>l64a</code> accepts big-endian integers but outputs little-endian strings. <p>... -
Upgrade radix
2020-12-05 18:27:25- Replace <code>Pool</code> with <code>Client, as in radix <code>Client</code> is abstract interface for pool, sentinel and redis cluster. - Refactor redis cache impl to use implicit pipelining to ... -
1010 Radix
2020-03-24 12:52:57#include<bits/stdc++.h> using namespace std;...int tag,radix; long long Map[256]; long long getnum(string s, int radix) { long long ans=0; for (int i=0; i<s.length(); i++) { a...#include<bits/stdc++.h> using namespace std; string n1,n2; int tag,radix; long long Map[256]; long long getnum(string s, int radix) {//进制运算 long long ans=0; for (int i=0; i<s.length(); i++) { ans=ans*radix+Map[s[i]]; if(ans<0) return -1; } return ans; } long long getlow(string s) {//计算数字最小可能的进制数 long long maxnum=0; for (int i=0; i<s.length(); i++) if (Map[s[i]]>maxnum)maxnum=Map[s[i]]; return maxnum+1; } long long Binary(long long low,long long high,string s,long long number) {//二分查找目标是否存在 while (low<high) { long long mid=(low+high)/2; long long result=getnum(s,mid); if (result>number||result==-1) high=mid; else if(result<number) low=mid; else if(result==number) return mid; } return -1; } void init() {//初始化0-9和a-z的数值 for (char c ='0'; c<='9'; c++) Map[c]=c-'0'; for (char c='a'; c<='z'; c++) Map[c]=c-'a'+10; } int main() { init(); cin>>n1>>n2>>tag>>radix; if(tag==2)//radix始终是n1的进制 swap(n1,n2); long long number1=getnum(n1,radix),low=getlow(n2),high=max(number1,low)+1,ans=Binary(low, high, n2, number1); if (ans!=-1) printf("%d",ans); else printf("Impossible"); return 0; }
-
radix sort
2018-01-22 10:20:44只要基数大于1,就可以得到正确的结果。 ...def findmaxdigit(num,radix): maxr=1 product=radix while product product*=radix maxr+=1 return maxr def radix_sort(A): num=len(A) maxd= -
radix sorting
2019-09-13 10:28:50radix sorting基于bucket sorting,先按照个位数排序,再按照十位数排序,再百位。。。 代码参考自 http://en.wikipedia.org/wiki/Radix_sort <script> function printArr(arr) ... -
radix在Character.MIN_RADIX与Character.MAX_RADIX之间
2018-11-09 11:14:08radix在Character.MIN_RADIX与Character.MAX_RADIX之间是指在 2~~36之间; 部分源码: public final class Character implements java.io.Serializable, Comparable<Character> { public static ... -
radix tree
2018-05-12 21:15:51最近看了看代码,研究了一下Linux内核中诸多数据结构中的radix tree。radix tree数据结构在Linux内核中实现的很精致,没怎么看的明白!今天先来简单记录一下这段时间的一些测试和想法。 获取实例代码 ... -
radix java_Radix Sort Java程序和算法
2020-09-12 06:17:26radix java This tutorial is about radix sort java program and algorithm.Here is a very basic and detailed description of algorithm that we follow to implement the radix sort in java. We mostly rely on... -
Radix Engineering Audit
2020-12-30 00:21:36<div><p>Radix needs improvements in performance, usability, and, internally, DX. <p>Let's do a time boxed audit and document of improvements ideas (say, no longer than 4 hours each). Once done, we... -
radix树
2019-09-24 02:28:00今天在学Linux内核页高速缓存时,学到了一种新的数据结构radix树(基数),经过分析,感觉此数据结构有点鸡肋,有可能是我理解不到位吧。 先来张图,给大家以直观的印象 当有一个key-value型的数据结构,它的key... -
radix sort_C语言中的Radix Sort程序
2020-09-12 16:54:34radix sortIn this tutorial you will learn about radix sort program in C. 在本教程中,您将学习C语言中的基数排序程序。 Radix sorting technique is one of the oldest techniques of sorting. 基数排序技术... -
Radix_Sort
2020-12-31 03:54:57Radix_Sort <p><strong>Submission Type Algorithm <p><strong>Submission Description Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place ... -
Radix sort Added
2020-12-09 00:37:52<div><h2>SHORT DESCRIPTION <p>Radix Sort added with readme file</p><p>该提问来源于开源项目:codeIIEST/Algorithms</p></div>
-
tp5微信小程序封装类库
-
TI BQ500511 和 BQ50002 无线充电评估板ALTIUM硬件原理图+PCB(4层板)文件.rar
-
Spark初探
-
智能停车场云平台(附vue+SpringBoot前后端项目源码)
-
【Python-随到随学】FLask第二周
-
增强用户体验让网站和APP更具动感的几点建议
-
Exe动态导入模型.rar
-
python中怎么取两个列表 集合的交集
-
Mysql高频面试题
-
Python Pandas 长宽表转换
-
SSH框架查询组合列返回Vo
-
Colors.rar
-
极品文件搜索工具推荐它没错 | 免索引全文信息检索工具
-
ffmpeg-win32-v3.2.4.zip
-
pytorch之dataloader深入剖析
-
Mycat 实现 MySQL的分库分表、读写分离、主从切换
-
分布式session之token解决方案实现
-
pandas 读取excel文件报错 AttributeError: ‘ElementTree‘ object has no attribute ‘getiterator‘
-
最全编程开发常用单词词汇
-
Java程序的运行机制