Other Languages - data structur - Asked By Najeeb Ullah on 23-Nov-11 10:04 AM

detail definition
Q: sprace metrics
Q: why it prohibited to  go to statement
Suchit shah replied to Najeeb Ullah on 23-Nov-11 11:10 AM
Sprace Metrics

In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros .  Conceptually, sparsity corresponds to systems which are loosely coupled. Consider a line of balls connected by springs from one to the next; this is a sparse system. By contrast, if the same line of balls had springs connecting each ball to all other balls, the system would be represented by a dense matrix. The concept of sparsity is useful in combinatorics and application areas such as network theory, which have a low density of significant data or connections.
Huge sparse matrices often appear in science or engineering when solving partial differential equations.
When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Operations using standard dense matrix structures and algorithms are slow and consume large amounts of memory when applied to large sparse matrices. Sparse data is by nature easily compressed, and this compression almost always results in significantly less computer data storage usage. Indeed, some very large sparse matrices are infeasible to manipulate with the standard dense algorithms.

The native data structure for a matrix is a two-dimensional array. Each entry in the array represents an element ai,j of the matrix and can be accessed by the two indices i and j. For an m×n matrix, enough memory to store at least (m×n) entries to represent the matrix is needed.
Substantial memory requirement reductions can be realized by storing only the non-zero entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to a native approach.
Formats can be divided into two groups: (1) those that support efficient modification, and (2) those that support efficient matrix operations. The efficient modification group includes DOK, LIL, and COO and is typically used to construct the matrix. Once the matrix is constructed, it is typically converted to a format, such as CSR or CSC, which is more efficient for matrix operations.

A sparse matrix is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse n×n matrix with cn entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factorize (with high probability and for large enough c; Gilbert et al. 1992).

If a matrix A is stored in ordinary (dense) format, then the command S = sparse(A) creates a copy of the matrix stored in sparse format. For example:

>> A = [0 0 1;1 0 2;0 -3 0]
A =
     0     0     1
     1     0     2
     0    -3     0
>> S = sparse(A)
S =
   (2,1)        1
   (3,2)       -3
   (1,3)        1
   (2,3)        2
>> whos
  Name      Size         Bytes  Class

  A         3x3             72  double array
  S         3x3             64  sparse array

Grand total is 13 elements using 136 bytes

Unfortunately, this form of the sparse command is not particularly useful, since if A is large, it can be very time-consuming to first create it in dense format. The command S = sparse(m,n) creates antex2html_wrap_inline707 zero matrix in sparse format. Entries can then be added one-by-one:


Why Goto statement is probhited ?

The following statements are generalizations; while it is always possible to plead exception, it usually (in my experience and humble opinion) isn't worth the risks.

  1. Unconstrained use of memory addresses (either GOTO or raw pointers) provides too many opportunities to make easily avoidable mistakes.
  2. The more ways there are to arrive at a particular "location" in the code, the less confident one can be about what the state of the system is at that point. (See below.)
  3. Structured programming IMHO is less about "avoiding GOTOs" and more about making the structure of the code match the structure of the data. For example, a repeating data structure (e.g. array, sequential file, etc.) is naturally processed by a repeated unit of code. Having built-in structures (e.g. while, for, until, for-each, etc.) allows the programmer to avoid the tedium of repeating the same cliched code patterns.
  4. Even if GOTO is low-level implementation detail (not always the case!) it's below the level that the programmer should be thinking. How many programmers balance their personal checkbooks in raw binary? How many programmers worry about which sector on the disk contains a particular record, instead of just providing a key to a database engine (and how many ways could things go wrong if we really wrote all of our programs in terms of physical disk sectors?

Footnotes to the above:

Re point 2, consider the following code:

a = b + 1
/* do something with a */

At the "do something" point in the code, we can state with high confidence that a is greater than b. (Yes, I'm ignoring the possibility of untrapped integer overflow. Let's not bog down a simple example.)

On the other hand, if the code had read this way:

...
goto 10
...
a = b + 1
10: /* do something with a */
...
goto 10
...

The multiplicity of ways to get to label 10 means that we have to work much harder to be confident about the relationships between a and b at that point. (In fact, in the general case it's undecideable!)

Re point 4, the whole notion of "going someplace" in the code is just a metaphor. Nothing is really "going" anywhere inside the CPU except electrons and photons (for the waste heat). Sometimes we give up a metaphor for another, more useful, one. I recall encountering (a few decades ago!) a language where

if (some condition) {
  action-1
} else {
  action-2
}

was implemented on a virtual machine by compiling action-1 and action-2 as out-of-line parameterless routines, then using a single two-argument VM opcode which used the boolean value of the condition to invoke one or the other. The concept was simply "choose what to invoke now" rather than "go here or go there". Again, just a change of metaphor.


Jitendra Faye replied to Najeeb Ullah on 23-Nov-11 11:07 PM
Ans2:


Disadvantages of Goto
 
Goto should not really be used in programs at . They have a tendancy to make code unstructured and they make programs difficult to manage when they become significantly large.

 

It is much better practice to use the other flow control constructs and procedures.




Jitendra Faye replied to Najeeb Ullah on 23-Nov-11 11:20 PM

Ans1:


A sparse matrix
is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse n×n matrix with cn entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factorize (with high probability and for large enough c; Gilbert et al. 1992).