Cadence® system design and verification solutions, integrated under our System Development Suite, provide the simulation, acceleration, emulation, and management capabilities.
System Development Suite Related Products A-Z
Cadence® digital design and signoff solutions provide a fast path to design closure and better predictability, helping you meet your power, performance, and area (PPA) targets.
Full-Flow Digital Solution Related Products A-Z
Cadence® custom, analog, and RF design solutions can help you save time by automating many routine tasks, from block-level and mixed-signal simulation to routing and library characterization.
Overview Related Products A-Z
Driving efficiency and accuracy in advanced packaging, system planning, and multi-fabric interoperability, Cadence® package implementation products deliver the automation and accuracy.
Cadence® PCB design solutions enable shorter, more predictable design cycles with greater integration of component design and system-level simulation for a constraint-driven flow.
An open IP platform for you to customize your app-driven SoC design.
Comprehensive solutions and methodologies.
Helping you meet your broader business goals.
A global customer support infrastructure with around-the-clock help.
24/7 Support - Cadence Online Support
Locate the latest software updates, service request, technical documentation, solutions and more in your personalized environment.
Cadence offers various software services for download. This page describes our offerings, including the Allegro FREE Physical Viewer.
Get the most out of your investment in Cadence technologies through a wide range of training offerings.
This course combines our Allegro PCB Editor Basic Techniques, followed by Allegro PCB Editor Intermediate Techniques.
Virtuoso Analog Design Environment Verifier 16.7
Learn learn to perform requirements-driven analog verification using the Virtuoso ADE Verifier tool.
Exchange ideas, news, technical information, and best practices.
The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information.
It's not all about the technlogy. Here we exchange ideas on the Cadence Academic Network and other subjects of general interest.
Cadence is a leading provider of system design tools, software, IP, and services.
Get email delivery of the Cadence blog featured here
In this article, I want to look at some ways to shuffle a list. In doing so, we'll also see how random numbers work in SKILL and a few examples of how to use them.
(onep (random 2))
(defun shuffle_a (data)
(sort (copy data)
(lambda (_a _b)
(onep (random 2)))))
(shuffle_a '(1 2))
(shuffle_a '(1 2 3))
(3 1 2)
(3 2 1)
Similarly, there are 24 permutations of (1 2 3 4), but (shuffle_a '(1 2 3 4)) returns one of the following eight permutations half of the time: (1 2 3 4), (1 2 4 3), (2 1 3 4), (2 1 4 3), (3 4 1 2), (3 4 2 1), (4 3 1 2), or (4 3 2 1). And it returns one of the other 16 permutations the other half of the time.
(1 2 3 4)
(shuffle_a '(1 2 3 4))
(1 2 4 3)
(2 1 3 4)
(2 1 4 3)
(3 4 1 2)
(3 4 2 1)
(4 3 1 2)
(4 3 2 1)
If you need a quick and dirty shuffle algorithm, shuffle_a is decent and easy to remember. But if you need a good shuffle algorithm, use a different one.
(defun shuffle_b (data)
((cddr data) ; more than 2 elements?
(let (left right)
(foreach item data
(if (zerop (random 2))
(push item left)
(push item right)))
(nconc (shuffle_b left)
((zerop (random 2))
The expression r = (random n) returns a number 0 <= r < n
r = (random n)
0 <= r < n
(defun shuffle_c (data)
(let ((n (length data))
(while (cdr data)
;; choose a random element: data[r]
r = (random n) ; randomly choose 0 <= r < n
p = (nthcdr r data)
;; add data[r] to shuffled
(push (car p)
;; remove data[r] from data
data = (nconc (ldiff data p)
;; decrement n
(push (car data) shuffled))
(remove 42 '(0 42 1 42 2 42 3))
(1 2 3)
(remove_once 42 '(0 42 1 42 2 42 3)) ==> (0 1 42 2 42 3)
You might implement remove_once as follows:
(defun remove_once (data item)
(let ((p (member item data)))
(nconc (ldiff data p)
mylist=(42 1 42 2 42 3)
(nthcdr 2 mylist) ==> (42 2 42 3)
left=(ldiff mylist right)
(defun random_element (data)
(nth (random (length data)) data)))
(defun shuffle_d (data)
e = (random_element data)
(push e shuffled)
data = (remove_once data e))
In addition we looked at two other functions:
Hi again Lakshmi,
supposing you want to sort the object according to the x-coordinate of their bounding-boxes. Here is how you might try it.
(sort gc (lambda (dbid1 dbid2)
(lessp (leftEdge dbid1~>bBox)
You might also take a look at another blog article which actually addresses this question with even more examples.
If you want to sort a list of dbobjects as in your question, which criteria do you want to use to decide how to order them? Do you want to sort them alphabetically according the the printed representation of their hex addresses. "db:0x14c97a79" < "db:0x14c97b79" ?
Or do you want to sort them by x coordinate of their origin? Or if it is a list of instances, do you want to sort them alphabetically by cellName?
First you have to decide on the comparison criteria.
If you really want to sort them alphabetically by printed representation, you can try something like the following.
(sort gc (lambda (dbid1 dbid2)
(alphalessp (sprintf nil "%L" dbid1)
(sprintf nil "%L" dbid2))))
Or if you prefer C-syntax, the following is equivalent.
sort( gc lambda( (dbid1 dbid2)
alphalessp( sprintf( nil "%L" dbid1)
sprintf( nil "%L" dbid2))))
Thanks for your question. I think you have space between "sort" and the opening paren.
Remember that in SKILL you are allowed to put the parenthesis either before or after the function name to denote a function call. Thus (B C) and B(C) are equivalent to each other. Furthermore (A B C) and A(B C) are equivalent to each other. Some people refer to these as LISP syntax vs C syntax.
The problem comes when you accidentally try to mix the two. SKILL does not get confused, but often the human being does.
CIW> (A B (C D))
CIW> (A B(C D))
The first is a call to A with 2 arguments, the second of which is a call to C.
The second is a call to A with 1 argument, namely a call to B.
In summary, if you want to call a function with some arguments, and you want to use C-syntax, don't put a space between the function name and the opening parenthesis. If you want SKILL to not care where you put spaces, use LISP-syntax.
NOW, back to your example.
CIW> sort (gc nil)
This tries to call sort with the return value of calling gc with nil as its argument.
But if you pass an argument to the gc function (the API for the SKILL garbage collector) that argument must be a string. This is what the messages mean.
*Error* gc: argument #1 should be a string (type template = "t") - nil
*Error* gc: argument #1 should be a string (type template = "t") - lessp
*Error* gc: argument #1 should be a string (type template = "t") - alphalessp
This explains what your error messages mean, but it does not yet answer your original question. I'll answer that in the next post.
To be continued.
How to sort this? required help
gc = geGetSelectedSet( )
(db:0x14c97a79 db:0x14c97aca db:0x14c97ad4 db:0x14c97ad1 db:0x14c97ace
db:0x14c97ab2 db:0x14c97acb db:0x14c97ac8 db:0x14c97ac5 db:0x14c97ac2
db:0x14c97abe db:0x14c97abf db:0x14c97ab4 db:0x14c97ab7 db:0x14c97ab8
*Error* sort: too few arguments (2 expected, 1 given) - ((db:0x1cdde44d db:0x1cdde44e db:0x1cdde449 db:0x1cdde446 db:0x1cdde445 ... ))
sort (gc nil)
sort (gc 'lessp)
sort (gc 'alphalessp)
Here's an implementation that runs in 5 seconds on a million items, and works by converting to a vector and then back to a list again at the end. I borrowed the algorithm from an implementation I found elsewhere...
(defun shuffle_e (data)
(letseq (j iinv (vec (listToVector data)) (len (length vec)))
(for i 1 len
(setq iinv (difference len i))
(setq j (random (add1 iinv)))
(setarray vec iinv (prog1 (arrayref vec j) (setarray vec j (arrayref vec iinv))))
Hi Andrew, thanks for the information about the profiling. I suspected the recursive algorithm might be a little faster. The results are indeed surprising.
You might be pretty successful by using an array and swapping each element with a randomly chosen element. I'd want to check the randomness of the resulting list to make sure. An algorithm such as the following would be where I'd start.
(defun shuffle_array (arr)
(let ((N (length arr)))
(for i 0 (sub1 N)
;; need to write this function: swap_elements
(swap_elements arr i (random N)))))
My gut feeling impression from looking at the implementations was that shuffle_c would suffer badly from performance compared with shuffle_b with large lists. So I did some profiling.
shuffle_b was able to shuffle a million entry list in about 17 seconds; shuffle_c I gave up after about 3 hours. From the profiling so far, it had spent over an hour of that time in gc. So I tried with a list of 10000 entries (2.4 secs), 100000 entries (221 seconds). So my wild guess is that it is of the order of N^2 - and so I might expect a million entries to take roughly 7 hours. shuffle_b was however 0.3 seconds for 10000, and 1.44s for 100000 (and 17 seconds for a million entries).
This doesn't really surprise me because doing those repeated nthcdr can't be very efficient.
I did wonder whether it could be made more efficient by using an array to store the data in the meantime - but the problem then is that you can't really remove entries from an array (such that the indices close up).