text:
T-61.5020 Statistical Natural Language Processing
Answers 7 -- Word sense disabiguation
Version 1.0

1.

Let's start from Bayes' theorem.

Now we are interested only in the order of probabilities, not the absolute values, so we can forget the normalization term :

In the equation the latter term is the prior for the word sense. It can be estimated for example by calculating how many of the words in the training corpus have appeared in the sense . For now we concentrate on the term .

Let's choose the nearest 10 words as the context:

The word we are studying would be in the middle, . Here, the order of the context words makes a difference, and this is marked by using the parentheses. Using these kind of feature vectors is in practice impossible, as two equal 10 word contexts are not likely to be found in the training or test sets. We approximate the model by assuming that the order is not significant (now using brackets):

Now we have:

Let's make the estimation easier by assuming that the words occur independently:

Finally, let's write the expression open:

In the last row the formula is written in logarithmic form. This can be done, because taking the logarithm does not affect the order of the values.

None of the used approximations is totally correct, but the roughest error is probably the one of independency of the context words. However, this is the way of getting an easily feasible method.

2.
Let's use the formula derived in the previous problem:

where are the words that occurred in the context.

We need two estimates: probability that the word in the context occurs with the sense , and prior probability . As we have equal number of occurrences for the senses sataa=rain and sataa=number, we can but set the prior to .

Maximum likelihood (ML) estimation is applied in the course book. In our problem we were asked to use priors, so let's define a small prior that all words are of equal probability to the probability , and add it to the estimators with coefficient . This can be thought as if every known word had already occurred 0.5 times in both context types. A large emphasises the meaning of the prior, and thus a small evidence from the training set does not change it much.

is the number of known words, 85.

a)
Let's calculate the estimators needed in the first test sentence:

We see that for the first sense, all probability mass comes from the prior. For the comparison number (i.e. unnormalized probability) we get

The same calculations for the number sense:

The comparison number is:

So according to the model, the number sense of sataa'' is more probable.

b)
As we saw before, we can leave out all the words that have not occurred in the contexts of either word, as they do not affect the order of the comparison numbers. Let's use the tool that changes all disambigous numbers to string num''. The needed probabilities are:

For the comparison numbers we get

This time the word seems to mean raining.

c)
For the third sentence,

For the comparison numbers we get

So it seems to be a number here.

d)
For the last sentence the given training data does not change the probabilities for any direction. And because the priors were equal, the model cannot make any decision here.

3.

Let's find the dictionary definitions for the words in the tested sentence. Those are compared to the dictionary definitions of two senses of the studied word. The meaning that has more mutual words with the words in the dictionary definitions of the other words (including the word itself) in the sentence is decided to be the correct one.

In this case, from the definition of ampuminen'', shooting, we find the words harjoitella'' and varusmies'' that are also in the test sentence. The word sarjatuli'' is found from the definition of kivääri'', so three points for shooting.

From the definition of ammuminen'', that is moo'ing, we find the word niityllä'', which is also in the test sentence. One point for moo'ing.

It seems that it is shooting for this one ().

4.

Let's see how many hits the Google will give:

 prices go up 111000 price goes up 88100 199100 prices slant 58 prices lean 2520 prices lurch 21 price slants 1 price leans 63 price lurches 114 2777

This example goes clearly for the sense go up''.

What about the next example? If we do the translation and search using the given word order, we will get no hits (excluding the hits for this exercise problem). So we try to find documents where the words may occur in any order:

 want shin hoof liver or snout 260 like shin hoof liver or snout 304 covet shin hoof liver or snout 219 desire shin hoof liver or snout 243 1026 want kick poke cost or suffer 43500

We see that the verb meanings of the words win here, altough the nouns would probable be more correct. All searches are not even needed, because the first one already produces more hits than all of the other senses together. In addition, most of the hits returned by the first four searches were from dictionaries.

As the senses shin, hoof, liver and snout are much rarer than the verbs, they are found much less. In this situation we should probably normalize the search in some way. This example was harder than the first one also because this time the sentence was not a common and fixed phrase.

5.

The problem is to estimate the probability of the sense when we know the context .

Let's use the Naive Bayes assumption presented in first problem, i.e. that the words in the context do not depend on each other:

### Initialization

Let's initialize the parameters:
• Set all the words to be equally probable for both sources, and add some noise . Without the noise the algorithm will not converge, as all the events have equal probabilities.

Here is the number of the known words.
• Set all senses to be of equal probability.

Here is the number of the different senses.

### E-step

• Calculate the probability of each sense for all contexts:

### M-step

• Estimate the new word probabilities using the sentence probabilities estimated in the E-step.

• Update the prior probabilities:

The convergence of the algorithm, as E- and M-steps are iterated, is illustrated in Figure 1. In this case the priors we kept at for first 15 iterations, which improved the stability. We see that the algorithm can separate the numbers and the trees. For sentences 8 and 9 the model overlearns and sets them only to one sense. If the amount of training data would be larger, also these estimates might be more feasible.

The same algorithm can be used to, e.g., separate a set of documents to their topics. In that case, the contexts would be the full documents.

[6.]

Here we present one possible example solution step by step. The most important points where we have made an arbitary decision that can increase inaccuracy and could be as well done otherwise, are marked with italics.

1)
The first step is to clean all the extra headlines, tags and markings away. Then we want to separate the contexts. Let the context for each word to be the full sentence where it occurs. Let's change some two words, e.g. sade'' (rain) and komissio'' (commission), to a common pseudoword. At the same time we can collect the correct answers for evaluation purpose.

2)
Let's change all words of the contexts to a vector form. Here we could use binary indicator vectors, but let's approximate those by setting a random 200-dimensional vector to each word. If the vector has enough dimensions, it is roughly orthogonal between all different words and the approximation is quite good.

3)
Let's assume that the order of the context words does not matter. Let's calculate the context for each word by summing up the vectors of the words in its context and dividing the sum by the number of the vectors.

4)
Let's cluster the context vectors using the self-organizing map (SOM). The number by clusters can be decided experimentally. For a small number of clusters it is easier to estimate the quality visually; a large number of clusters can give a finer separation.

5)
Last we need to evaluate the quality of the clustering. For unsupervised methods this is sometimes hard, but in this case we can do the following: First we look if words with different senses went nicely to different clusters using the correct senses from the training set. This does not prove much, because if we chose as many clusters as we have words in the training set, we would get automatically the best result. Instead, we use the training samples to label each cluster. This means that the cluster that has more items of some sense A (relative to the size of the training set for both senses) alleges that all samples that go nearby have surely the sense A. We try the test set against these senses and see how many are correct.

Using the method described above we got the results in Table 1. Here we used a map of size . If no correct answers are available, it is easier to evaluate the result when we have small number of groups. For example, for words sade'' and komissio'', the results for a map were 59% and 98%. In Figure 2 we have the grouping of words sade'' and komissio'' for the map.

 training test correct % correct % correct % correct % Lappi Pariisi 63 55 61 53 sade komissio 66 93 66 92 Venäjä tammikuu 80 60 78 60 Halonen TPS 62 74 63 70 leijona ydinvoima 70 55 75 48

svirpioj[a]cis.hut.fi


text:
Show Summary Details
More options …

# Journal of Mathematical Cryptology

Managing Editor: Magliveras, Spyros S. / Steinwandt, Rainer / Trung, Tran

Editorial Board: Blackburn, Simon R. / Blundo, Carlo / Burmester, Mike / Cramer, Ronald / Gilman, Robert / Gonzalez Vasco, Maria Isabel / Grosek, Otokar / Helleseth, Tor / Kim, Kwangjo / Koblitz, Neal / Kurosawa, Kaoru / Lauter, Kristin / Lange, Tanja / Menezes, Alfred / Nguyen, Phong Q. / Pieprzyk, Josef / Rötteler, Martin / Safavi-Naini, Rei / Shparlinski, Igor E. / Stinson, Doug / Takagi, Tsuyoshi / Williams, Hugh C. / Yung, Moti

CiteScore 2018: 1.41

SCImago Journal Rank (SJR) 2018: 0.342
Source Normalized Impact per Paper (SNIP) 2018: 1.076

Mathematical Citation Quotient (MCQ) 2018: 0.75

Online
ISSN
1862-2984
See all formats and pricing
More options …
Volume 10, Issue 2

# Another look at normal approximations in cryptanalysis

Subhabrata Samajder
/ Palash Sarkar
Published Online: 2016-05-18 | DOI: https://doi.org/10.1515/jmc-2016-0006

## Abstract

Statistical analysis of attacks on symmetric ciphers often requires assuming the normal behaviour of a test statistic. Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important normal approximations that have been made in the literature. To do this, we use the Berry–Esséen theorem to derive explicit bounds on the approximation errors. A basic mathematical requirement is that such approximation errors should be within reasonable bounds, a point which appears to have been overlooked in many of the earlier works on statistical aspects of cryptanalysis. Interpreting the error bounds in the cryptanalytic context yields several surprising results. One important implication is that this puts in doubt the applicability of the order statistics based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we are able to recover all of these results by utilising the hypothesis testing framework. This, however, necessitates using normal approximations for the ${\chi }^{2}$ and the LLR test statistics considered in earlier works. These approximations themselves have issues which seem to be difficult to resolve satisfactorily. More generally, the message of our work is that all cryptanalytic attacks should properly derive and interpret the error bounds for any (normal) approximation that is made.

MSC: 94A60; 11T71; 68P25; 62P99

## References

• 1

M. A. Abdelraheem, M. Ågren, P. Beelen and G. Leander, On the distribution of linear biases: Three instructive examples, Advances in Cryptology (CRYPTO 2012), Lecture Notes in Comput. Sci. 7417, Springer, Berlin (2012), 50–67. Google Scholar

• 2

T. Baignères, P. Junod and S. Vaudenay, How far can we go beyond linear cryptanalysis?, Advances in Cryptology (ASIACRYPT 2004), Lecture Notes in Comput. Sci. 3329, Springer, Berlin (2004), 432–450. Google Scholar

• 3

T. Baignères, P. Sepehrdad and S. Vaudenay, Distinguishing distributions using Chernoff information, Provable Security, Lecture Notes in Comput. Sci. 6402, Springer, Berlin (2010), 144–165. Google Scholar

• 4

V. Bentkus, Dependence of the Berry–Esséen estimate on the dimension, Lithuanian Math. J. 26 (1986), 110–114. Google Scholar

• 5

A. C. Berry, The accuracy of the Gaussian approximation to the sum of independent variates, Trans. Amer. Math. Soc. 49 (1941), 122–136. Google Scholar

• 6

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Advances in Cryptology (CRYPTO'90), Lecture Notes in Comput. Sci. 537, Springer, Berlin (1990), 2–21. Google Scholar

• 7

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology 4 (1991), 3–72. Google Scholar

• 8

A. Biryukov, C. De Cannière and M. Quisquater, On multiple linear approximations, Advances in Cryptology (CRYPTO 2004), Lecture Notes in Comput. Sci. 3152, Springer, Berlin (2004), 1–22. Google Scholar

• 9

C. Blondeau, A. Bogdanov and G. Leander, Bounds in shallows and in miseries, Advances in Cryptology (CRYPTO 2013), Lecture Notes in Comput. Sci. 8042, Springer, Berlin (2013), 204–221. Google Scholar

• 10

C. Blondeau and B. Gérard, Multiple differential cryptanalysis: Theory and practice, Fast Software Encryption, Lecture Notes in Comput. Sci. 6733, Springer, Berlin (2011), 35–54. Google Scholar

• 11

C. Blondeau, B. Gérard and K. Nyberg, Multiple differential cryptanalysis using LLR and ${\chi }^{2}$ statistics, Security and Cryptography for Networks, Lecture Notes in Comput. Sci. 7485, Springer, Berlin (2012), 343–360. Google Scholar

• 12

C. Blondeau, B. Gérard and J.-P. Tillich, Accurate estimates of the data complexity and success probability for various cryptanalyses, Des. Codes Cryptogr. 59 (2011), 3–34.

• 13

A. Bogdanov and E. Tischhauser, On the wrong key randomisation and key equivalence hypotheses in Matsui's algorithm 2, Fast Software Encryption, Lecture Notes in Comput. Sci. 8424, Springer, Berlin (2014), 19–38. Google Scholar

• 14

J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, J. Math. Crypt. 1 (2007), 221–242. Google Scholar

• 15

F. C. Drost, W. C. M. Kallenberg, D. S. Moore and J. Oosterhoff, Power approximations to multinomial tests of fit, J. Amer. Statist. Assoc. 84 (1989), 130–141. Google Scholar

• 16

C.-G. Esséen, On the Liapounoff limit of error in the theory of probability, Ark. Mat. Astron. Fys. A28 (1942), 1–19. Google Scholar

• 17

C.-G. Esséen, A moment inequality with an application to the central limit theorem, Scand. Actuar. J. 1956 (1956), 160–170. Google Scholar

• 18

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 2, John Wiley & Sons, New York, 2008. Google Scholar

• 19

C. Harpes, G. G. Kramer and J. L. Massey, A generalization of linear cryptanalysis and the applicability of Matsui's piling-up lemma, Advances in Cryptology (EUROCRYPT'95), Lecture Notes in Comput. Sci. 921, Springer, Berlin (1995), 24–38. Google Scholar

• 20

M. Hermelin, J. Y. Cho and K. Nyberg, Multidimensional extension of Matsui's algorithm 2, Fast Software Encryption, Lecture Notes in Comput. Sci. 5665, Springer, Berlin (2009), 209–227. Google Scholar

• 21

N. L. Johnson, S. Kotz and N. Balakrishnan, Continuous Univariate Distributions, Vol. 1, 2nd ed., John Wiley & Sons, New York, 1994. Google Scholar

• 22

N. L. Johnson, S. Kotz and N. Balakrishnan, Continuous Univariate Distributions, Vol. 2, 2nd ed., John Wiley & Sons, New York, 1995. Google Scholar

• 23

P. Junod, On the optimality of linear, differential, and sequential distinguishers, Advances in Cryptology (EUROCRYPT 2003), Lecture Notes in Comput. Sci. 2656, Springer, Berlin (2003), 17–32. Google Scholar

• 24

P. Junod and S. Vaudenay, Optimal key ranking procedures in a statistical cryptanalysis, Fast Software Encryption, Lecture Notes in Comput. Sci. 2887, Springer, Berlin (2003), 235–246. Google Scholar

• 25

B. S. Kaliski Jr and M. J. B. Robshaw, Linear cryptanalysis using multiple approximations, Advances in Cryptology (Crypto'94), Lecture Notes in Comput. Sci. 839, Springer, Berlin (1994), 26–39. Google Scholar

• 26

L. R. Knudsen, Truncated and higher order differentials, Fast Software Encryption, Lecture Notes in Comput. Sci. 1008, Springer, Berlin (1995), 196–211. Google Scholar

• 27

G. Leander, On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN, Advances in Cryptology (EUROCRYPT 2011), Lecture Notes in Comput. Sci. 6632, Springer, Berlin (2011), 303–322. Google Scholar

• 28

I. Mantin and A. Shamir, A practical attack on broadcast RC4, Fast Software Encryption, Lecture Notes in Comput. Sci. 2355, Springer, Berlin (2002), 152–164. Google Scholar

• 29

M. Matsui, Linear cryptanalysis method for DES cipher, Advances in Cryptology (EUROCRYPT'93), Lecture Notes in Comput. Sci. 765, Springer, Berlin (1993), 386–397. Google Scholar

• 30

M. Matsui, The first experimental cryptanalysis of the data encryption standard, Advances in Cryptology (CRYPTO'94), Lecture Notes in Comput. Sci. 839, Springer, Berlin (1994), 1–11. Google Scholar

• 31

S. Murphy, The independence of linear approximations in symmetric cryptanalysis, IEEE Trans. Inform. Theory 52 (2006), 5510–5518. Google Scholar

• 32

S. Murphy, F. Piper, M. Walker and P. Wild, Likelihood estimation for block cipher keys, Technical Report RHUL-MA-2006-3, Royal Holloway, University of London, 1995. Google Scholar

• 33

V. V. Sazonov, On the multi-dimensional central limit theorem, Sankhya A 30 (1968), 181–204. Google Scholar

• 34

A. A. Selçuk, On probability of success in linear and differential cryptanalysis, J. Cryptology 21 (2008), 131–147. Google Scholar

• 35

A. Tardy-Corfdir and H. Gilbert, A known plaintext attack of FEAL-4 and FEAL-6, Advances in Cryptology (CRYPTO'91), Lecture Notes in Comput. Sci. 576, Springer, Berlin (1991), 172–181. Google Scholar

• 36

I. S. Tyurin, An improvement of upper estimates of the constants in the Lyapunov theorem, Russian Math. Surveys 65 (2010), 201–202. Google Scholar

• 37

A. M. Walker, A note on the asymptotic distribution of sample quantiles, J. R. Stat. Soc. Ser. B. Stat. Methodol. 30 (1968), 570–575. Google Scholar

## About the article

Revised: 2016-04-27

Accepted: 2016-04-27

Published Online: 2016-05-18

Published in Print: 2016-06-01

Citation Information: Journal of Mathematical Cryptology, Volume 10, Issue 2, Pages 69–99, ISSN (Online) 1862-2984, ISSN (Print) 1862-2976,

Export Citation

© 2016 by De Gruyter.

format: plain


text:
# Place value blocks

### Problem

Which place value model shows 2923?
Please choose from one of the following options.


text:
# Set qualification - Microstrategy

A set qualification allows you to create a set based on either a metric qualification or a relationship qualification.

Set qualification: metric qualification

Metric qualifiers enable you to restrict metric values based on value, rank, or rank percentage. Metric qualifiers restrict the amount of data used to calculate the metrics on a report. For example, a store manager might want to see sales numbers for products whose current inventory levels fall below a certain level. This report will not necessarily display the inventory figures for those products.

Output level

The output level specifies the level at which the metric is calculated for the qualification. For example, if the metric qualification is Sales > 1000, Sales could mean sales per day, month, year, store, region, and so on. Creating a set qualification with an output level of store is equivalent to having a fixed list of stores, if you knew which ones met the metric qualification, in a simple attribute qualification. However, the list of stores in the qualification is generated dynamically.

The output level can be specified in several ways.

• An attribute list allows you to specify the exact set of attributes (such as day, month, or year) to use as the output level.
• Report level means that the output level is defined by the level of the report that contains the metric qualification. For example, if the lowest level of the report is year and the output level is set to report level, the metric is calculated for the year.
• Metric level means that the output level is defined by the level, or dimensionality, of the metric itself, regardless of the level of the report.
• The None selected option calculates the results at the report level if any of the following is true:
• The metric is a compound metric.
• The metric’s dimensionality is set to report level.
• The metric’s dimensionality is set to nothing.

Otherwise, the metric's dimensionality is used.

If you do not select an output level, the None selected option is used by default.

Break by

This advanced function of a metric qualification allows you to choose the attribute level at which to restart counting rank or percent values for a metric. This level must be greater than or equal to the level of aggregation for the metric itself, as shown in the following example.

Given the following data:

If you specify “Break by Market,” the ranking counter is reset for each market (in descending order).

If you specify “Break By Region,” the ranking counter is reset for each region (in this example, as there is only one region, the counter is not reset).

Merge attribute qualifications

The Advanced button allows you to specify whether existing attribute qualifications should be merged into the calculation of the metric qualification. By default, this option is selected, combining the qualifications.

A metric qualification is contained in a separate pass of SQL, creating a temporary table or “mini-report.” If the qualifications are merged, attribute qualifications are added to that pass of SQL. If they are not merged, the attribute qualifications are not included in the metric qualification. They instead appear in the main SQL pass.

For example, a report shows revenue by region. The report 2002 and the metric qualification of revenue over $1 million. If the default is kept, the qualifications are merged. Only 2002 revenue is considered when the metric checks for revenue over$1 million. The report results are:

In contrast, if the qualifications are not merged, revenue is calculated for all time before the metric qualification is evaluated. However, only revenue from the year 2002 is displayed on the report. As shown in the following sample,regions are included that do not have $1 million of revenue in 2002, but do have$1 million of revenue across time.

Besides affecting the report results, merging the qualifications reduces the amount of data a calculation must process.

Metric-to-metric comparison

Metric-to-metric comparisons allow you to create reports that dynamically compare the values of two metrics. For example, you can create a report that restricts the data torevenue greater than last quarter’s revenue.

Create a report that displays the revenue for Call centers Atlanta, San Diego, and Miami for each quarter during the year 2002. To do this, create one filter that includes the call centers Atlanta, San Diego and Miami and another filter that includes the year 2002. For step-by-step directions on creating a filter, see the online help.

When you execute the report, it looks like the following:

Now, create a revenue metric that calculates the revenue for the previous quarter and save it as RevenueLastQuartermetric. Create a metric-to-metric comparison filter that uses the Revenue metric. Choose the Function as Metric Value,and Operator as Greater than. Choose the Value as Metric and browse to select the newly created metric Revenue Last Quarter. Save the filter LastQuarter. The report,when re-executed with the LastQuarter filter,now looks like the following:

Note that only those revenues whose values are greater than the revenues of the previous quarter are displayed on the report.

Set qualification: relationship qualification

Relationship qualification allows you to create a link between two attributes and place a filter on that relationship. It allows you to create a set of elements from an attribute based on its relationship with another attribute. For example, relationship filtering allows you to create a report that shows you all the stores selling Nike shoes in the Washington, DCarea or all customers who have checking accounts but no saving accounts.

You can create relationship filters using either Set qualification or Advanced qualification in the Filter Editor. Set qualification provides an interface to guide you through the process, while you must enter commands in Advanced Qualification. The syntax for the Advanced qualification is described in Advanced qualification: relationship filters.

You have the following options while creating a relationship qualification:

• Output level is the level at which the set is calculated. You can select the attribute(s) for the output level.
• Filter Qualification defines the input filtering criteria, that is, the relationship on which to qualify. You can select an existing filter or create a new filter.
• Relate output level and filter qualification by is the relation between the attributes in the output level and filter qualification. The relation can be a fact, a table, or an empty filter. If the relationship is left empty, the schema is used to select the appropriate table.

For example, to create a report that shows all the stores selling Nike shoes in the Washington, DC area, you need to set the output level to Stores, the filter qualification to Nike shoes and Region, and the relation to the fact Sales.

Metric qualification prompt

A metric qualification prompt allows you to select a function, or an operator, or specify the value for a metric, when you run a report. You can create the following types of metric qualification prompts:

• Qualify on a metric prompt allows you to qualify on a metric. You can choose a metric by specifying a single metric to use when the report is run or by specifying a search object to restrict the list of metrics from which you can choose a metric, when a report is run.
• Metric Object prompt allows you to select one or more metrics that meet specific criteria when a report is run. For example, you could use a search to return a list of all metrics that contain a certain fact. From that list of metrics, you can then choose the metrics that you want to see on the report.
• Value prompt allows you to select a single value on which to qualify, such as a date, a specific number, or a specific text string.


text:
# In which one of the following, the dispersed phase is a liquid?

(a) whipped cream

(b) foam rubber

(c) paint

(d) cloud

Clouds are water dispersed in air.


text:
Browse Questions

The angle at which first order reflection will occur when X-ray of wavelength $1.54A^{\large\circ}$ are diffracted by the atoms of a crystal ; the interplanar distance is $4.04A^{\large\circ}$

$(a)\;22^\circ20'\qquad(b)\;10^\circ59'\qquad(c)\;33^\circ32'\qquad(d)\;15^\circ24'$

Can you answer this question?

$\lambda = 2d\sin\theta$
$1.54 = 2\times4.04\sin\theta$
$\theta = \sin^{-1}(0.191)$
$= 10.98^{\large\circ}$
$=10^{\large\circ}59'$
Hence answer is (b)
answered Feb 27, 2014


text:
Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.approximation.treewidth.treewidth_min_degree¶

treewidth_min_degree(G)[source]

Returns a treewidth decomposition using the Minimum Degree heuristic.

The heuristic chooses the nodes according to their degree, i.e., first the node with the lowest degree is chosen, then the graph is updated and the corresponding node is removed. Next, a new node with the lowest degree is chosen, and so on.

Parameters
GNetworkX graph
Returns
Treewidth decomposition(int, Graph) tuple

2-tuple with treewidth and the corresponding decomposed tree.


text:
Session 121 - Molecular Clouds/Star Formation.
Oral session, Saturday, January 10
Georgetown,

## [121.01] Far-Infrared and Submillimeter Polarization of OMC-1 -- Evidence for Magnetically Regulated Star Formation

D. A. Schleuning (U. Chicago)

This paper presents large scale polarization maps (8' \times 8') of the Orion molecular cloud (OMC-1) at far-infrared (100 \mum; 35'' resolution) and submillimeter (350 \mum; 18'' resolution) wavelengths. The magnetic field shows a pinch at scales less than 1/2 pc with a centroid that is on the OMC-1 ridge, a site of high mass star formation. We infer that gravitational collapse pulled the magnetic field into an hourglass shape. We estimate that the magnetic, kinetic, and gravitational energies are in equipartition on the ridge and that the magnetic energy dominates in the surrounding ambient envelope. We consider a model in which the ridge and thus high mass stars gravitationally collapsed out of a cloud that was initially supported by the magnetic field. At flux peaks there is a reduction in the percent polarization. This effect is discussed in relation to temperature, optical depth, and wavelength.


text:
How to prove the following about a group G?

How does one prove that:

for all $a\in G$, where $G$ is a group (not necessarily abelian) $a^{|G|} = 1_G$.

Solutions Collecting From Web of "How to prove the following about a group G?"

First, your restrict yourself to finite groups (otherwise, the statement does not make sense).

Then, you apply Lagrange’s Theorem to the subgroup $\langle a \rangle$ to conclude that the order of $a$ divides $|G|$.

This is a standard fact, which i think is proved in All abstract algebra books. Here is the proof, given in the book by Herstein. See Corollary 2.

Corollary 1: If $G$ is a finite group, and $a \in G$, then $o(a) \mid o(G)$.

Proof. Consider the cyclic subgroup generated by $a$, consisting of $a,a^{2},a^{3},\cdots,$. Since $a^{o(a)}=e$, therefore, this subgroup has atmost $o(a)$ elements. If it has fewer elements, then $a^{i}=a^{j}$, for some integers $0 \leq i < j < o(a)$. Then $a^{j-i}=e$, yet $0< j-i < o(a)$, which contradicts the meaning of $o(a)$. Thus the cyclic subgroup generated by $a$ has $o(a)$ elements, and hence by Lagrange’s theorem $o(a) \mid o(G)$.

Corollary 2: If $G$ is a finite group and $a \in G$, then $a^{o(G)}=e$.

Proof. By Corollary 1, we have $o(a) \mid o(G)$ which implies $o(G)=k \cdot o(a)$, therefore $a^{o(G)}=a^{k \cdot o(a)} = (a^{o(a)})^{k} = e^{k}=e$.


text:
Natural coherent sheaves on algebraic varieties - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T01:54:28Z http://mathoverflow.net/feeds/question/57682 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties Natural coherent sheaves on algebraic varieties vic 2011-03-07T15:21:12Z 2011-03-08T09:01:59Z
Let X be a smooth projective variety of dimension d over an algebraically closed field k. Can you please list some examples of natural locally free or coherent sheaves that you can always construct on X, regardless whether X has some particular structure or is of general type?

I can only name the two obvious examples: the structural sheave and the sheaf of differentials (and obvious combinations of them, of course, which do not count).

I can believe that these are the only ones for curves, as the genus is the only discrete invariant available.

What about surfaces, for instance?
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57683#57683 Answer by Karl Schwede for Natural coherent sheaves on algebraic varieties Karl Schwede 2011-03-07T15:30:49Z 2011-03-07T15:30:49Z
In characteristic $p > 0$ one can take the Frobenius (iterated) pushforward of the structure sheaf and various sheaves of differentials. These are always locally free by an old result of Kunz. For toric varieties (and related varieties) you can explicitly compute these Frobenius pushforward sheaves, see a paper by Thomsen.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57689#57689 Answer by David Speyer for Natural coherent sheaves on algebraic varieties David Speyer 2011-03-07T16:17:02Z 2011-03-07T16:17:02Z
This is really a comment that is too long for the comment box, in an attempt to more clearly define the problem.

I assume that "obvious combinations" includes the result of applying any Schur functor to $T^* X$ and $T_* X$, and any direct sum of such.

Does it include nontrivial extensions of such? Because there are some. For example: Let $\mathcal{I}$ be the ideal sheaf of the diagonal on $X \times X$. Then we have a short exact sequence on $X \times X$: $$0 \to \mathcal{I}/\mathcal{I}^2 \to \mathcal{O}/\mathcal{I}^2 \to \mathcal{O}/\mathcal{I} \to 0.$$ Pushing this to the first copy of $X$, we have a short exact sequence: $$0 \to \Omega^1(X) \to A \to \mathcal{O}_X \to 0$$ where $A$ is an extension which is usually nontrivial. (In particular, it is nontrivial if any of the Chern classes of $T^* X$ are nontrivial.) You can play similar games with higher tensor powers of $\mathcal{I}$ and get other canonical nontrivial extensions between tensor powers of $T^* X$.

Let me suggest breaking your question up into several parts, of successively greater optimism. I will leave the word "canonical" undefined for now. For the reasons Karl mentions, all of these are guesses are in characteristic zero.

Guess 1: The only canonical classes in $K_0(X)$ are integer combinations of the Schur functors of $T_* X$ and $T^* X$.

Guess 2: The only canonical classes in $K_0(X)$ which are classes of vector bundles are nonnegative integer combinations of the Schur functors of $T_* X$ and $T^* X$.

Guess 3: Every canonical method of assigning a vector bundle to an algebraic variety has an filtration whose successive quotients are the Schur functors of $T_* X$ and $T^* X$.

Guess 4, somewhat vague: All of the extensions of vector bundles occurring in guess 3 are built from constructions on nilpotent thickenings of the diagonal in $X \times X$.

I don't know whether any of these guesses are true, but they might help focus the discussion.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57690#57690 Answer by Qfwfq for Natural coherent sheaves on algebraic varieties Qfwfq 2011-03-07T16:25:34Z 2011-03-07T16:25:34Z
Do $\mathcal{D}$-modules, such as the sheaf of rings of differential operators $\mathcal{D}_X$ itself, count as combinations?

And the jet bundles $\mathrm{Jet}^k_X$ ?
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57693#57693 Answer by Sándor Kovács for Natural coherent sheaves on algebraic varieties Sándor Kovács 2011-03-07T16:44:01Z 2011-03-08T01:24:52Z
I'll put out the following possibly bold, possibly totally stupid conjectures. In any case, the statements below are not intended as mathematically rigorous statements, but may have some truth in them. Cheers!

Conjecture 1 Any naturally defined coherent sheaf on all smooth projective varieties is related to the sheaf of differentials via tensor operations and up to torsion.

A more concrete version is

Conjecture 2 Let $\mathscr L_X$ be a naturally defined line bundle on all smooth projective varieties $X$. Then some tensor power (possibly negative or zero) of $\mathscr L_X$ agrees with some tensor power of the canonical bundle.

Remark Jason pointed out that there are naturally defined torsion line bundles and Arend's idea of defining sheaves as push-forwards would produce sheaves supported on proper closed subvarieties. This is the main motivation for the "up to torsion" part of the first conjecture and for taking powers of the natural line bundle and the canonical bundle. Also notice that David Ben-Zvi's construction produces sheaves that satisfy these conjectures and the extensions in David Speyer's answer produce sheaves whose determinants are powers of the canonical sheaf.

To get to Conjecture 1 from Conjecture 2 one could argue the following way. Since the claim is "up to torsion" we can mod out by the torsion and assume that our sheaf is torsion-free. Now since we are on a smooth variety this implies that it is locally free in codimension $2$ and actually, again by the "up to torsion" principle, we may assume that it is reflexive, that is, take the reflexive hull, or in other words, the push-forward of the restriction to the open set where it is a locally free sheaf. In other words, we may perform all tensor operations as if we had locally free sheaves and in particular, the (reflexive hull of the) determinant will be a line bundle. In other words, up to torsion, we obtained a natural line bundle. If that is either the structure sheaf or the canonical bundle, then we're in business.

The reasoning I can offer for Conjecture 2 is the following: If there is a natural line bundle, then we can ask whether it is ample (or its inverse is) and for those varieties that it is we obtain a natural embedding (after taking some power). Once we have this we can look at the corresponding Hilbert schemes and try to construct moduli spaces. For those varieties on which this mysterious line bundle is not ample we can still define a corresponding Kodaira dimension and study Iitaka fibrations and eventually work toward a corresponding classification theory. I don't think any of this has happened except for the version using the canonical sheaf. I believe that suggests that there are no other non-trivial natural line bundles.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57698#57698 Answer by Johannes Ebert for Natural coherent sheaves on algebraic varieties Johannes Ebert 2011-03-07T17:01:06Z 2011-03-07T17:01:06Z
The jet bundle $J_k (X)$ has been mentioned several times. It is NOT a ''combination'' of the tangent bundle, because it cannot be recovered from the tangent bundle (not by bundle techniques, at least). To fix the notation, a point in $J_k (X)$ over $x$ is a germ of a rational function on $X$, and two are equivalent if they coincide up to order $k$ at $x$. There are epimorphisms $J_k (X) \to J_{k-1}$ with kernel $Sym^k (T^{\ast} X)$, and of course $J_1 (X) = T^{\ast}(X)$. Dually, we can consider jet bundles of germs of curves into $X$. These jet bundles give some more credibility to the four guesses that David made.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57699#57699 Answer by David Ben-Zvi for Natural coherent sheaves on algebraic varieties David Ben-Zvi 2011-03-07T17:24:23Z 2011-03-07T17:24:23Z
One formal approach to a problem like this is motivated by the "formal geometry" of Gelfand-Fuchs (which is the subject of other MO questions). We can define a "natural bundle" on a class of spaces to be one associated to a representation of a structure group of the given geometry. This is a common approach in differential geometry, where there's a lot known about natural differential operators etc. But in any case in the current context we can define a natural bundle on smooth n-dimensional varieties as one associated to a representation of the group of changes of coordinates on a formal n-dimensional disc. Every smooth variety has a canonical principal bundle for this group (with fiber over $x\in X$ the variety of isomorphisms between the completion of $X$ at $x$ and the formal disc), and so given a representation of the group we get a vector bundle on any variety of the given dimension.

All of the bundles discussed in the answers above are of this form (including jet bundles, sheaves of differential operators etc). If you take this as a definition of a natural bundle it's easy to prove the conjecture that they're all extensions of powers of bundles of forms: the group of changes of coordinates is an extension of $GL_n$ (the structure group of the tangent bundle) by a pro-unipotent group (changes of coordinate with derivative the identity). Hence all representations have filtrations with associated graded bundles associated to the (frame bundle of the) tangent bundle in the usual sense (ie all the Schur functors of the tangent bundle, like forms).

Edit: it's interesting to note that if we take representations of this group which extend to the Lie algebra of all derivations of formal power series in n variables (ie we have an action of $\partial_x$'s on the module as well) we get "all" natural flat bundles on smooth varieties --- such as the sheaves of all jets or all differential operators.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57729#57729 Answer by Jason Starr for Natural coherent sheaves on algebraic varieties Jason Starr 2011-03-07T20:59:30Z 2011-03-07T20:59:30Z
What about the locally free sheaf which is the direct sum of all n-torsion invertible sheaves, for some fixed integer n? Of course on many smooth, projective varieties this is zero. But it is a "canonically defined" locally free sheaf which is sometimes nonzero. And I see no obvious way to build this from the structure sheaf or the cotangent sheaf.
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57738#57738 Answer by ABayer for Natural coherent sheaves on algebraic varieties ABayer 2011-03-07T21:54:42Z 2011-03-07T21:54:42Z
Given a map $f \colon X \to Y$, there are of course various ways to construct sheaves on $X$ from $f$ - e.g. relative differentials, or any other sheaf obtained from the cotangent complex of $f$, etc.

So any canonically constructed map gives canonically constructed sheaves. An example would be the Albanese map. For varieties of general type, one could also construct sheaves associated to the map to the canonical model (but of course this needs more care, as this is only a rational map).

One could also construct sheaves on $X$ from natural morphisms to $X$, but I don't right away see a way to get a coherent sheaf in that manner. (A cheap way to get a quasi-coherent sheaf would, for example, be to take the push-forward of the structure sheaf of the universal curve of the union of all Kontsevich spaces of stable maps from curves of a fixed genus $g$.)
 http://mathoverflow.net/questions/57682/natural-coherent-sheaves-on-algebraic-varieties/57796#57796 Answer by Piotr Achinger for Natural coherent sheaves on algebraic varieties Piotr Achinger 2011-03-08T09:01:59Z 2011-03-08T09:01:59Z
In characteristic $p>0$, you can not only take push-forwards by the Frobenius (see Karl Schwede's answer), but also pull-backs.

Of course pulling the structure sheaf back gives the structure sheaf, but you can pull-back higher rank bundles, e.g. $\Omega_X^i$. The bundles $F^{s*} \Omega^i_X$ have been studied in the paper

Brückmann, P., Müller, D. "Birational invariants in the case of prime characteristic". Manuscripta Math. 95 (1998), no. 4, 413–429. (MR1618186)

As the title suggests, they produce birational invariants generalizing the plurigenera.


text:
Programming puzzles: processing lists!
06-12-2017, 07:46 PM (This post was last modified: 06-13-2017 10:24 AM by pier4r.)
Post: #141
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Neat addition. And yes the revlist works.

So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist) . wrong, the code had a bug.
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)

So if exploding a list with userRPL gets a speed (maybe only for 100 elements, I need to test with 1000) comparable to dolist/dosubs and way better than the compact TAIL + HEAD (those may be few commands but I beleive are intensive), I was thinking that exploding the list and handling it with sysRPL would be super fast, like 3 times faster.

Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

if the "headTail" procedure holds its speed, it is a great replacement for dosubs/dolists for iterations, at least in userRPL.
Also using a for is not as bad as I thought. Going for 1000 elements now.

Of course, if you see other ways (debug friendly) to iterate over a list, please tell me!

Code:
 headListHelp "input: L1: list output: L2: list without head element L1: head element"      headList   \<<     @given a list in input, leaves on level1 the first element     @ and on level 2 the rest of the list.          @0        @numEl     \->     @external input     list     @local input     @numEl        @elements in the list.     \<<       list OBJ\-> 1 - \->LIST         @reducing the number of elements of 1 for the new list         @we have the tail on level 2       SWAP         @now the head element is on the level 1 stack     \>>   \>> testIterationSpeed     @ testing the efficiency of different iteration approaches,     @ given that DOLIST and DOSUBS although fast are not     @ so debug friendly especially when nested     @ The approach tested the fact to get an element from the list     @ that then can be processed     \<<       {} "baseList" DROP       100 "baseListSize" DROP       {} "resListDosubs" DROP       {} "resListDolist" DROP       {} "resListForGet" DROP       {} "resListStartGeti" DROP       {} "resListStartheadList" DROP       {} "resListStarttailhead" DROP       {} "resListStartLrot" DROP       0 "temp" DROP              \->       @input       iterations              @localVar       baseList       baseListSize       resListDosubs       resListDolist       resListForGet       resListStartGeti       resListStartheadList       resListStarttailhead       resListStartLrot       temp       \<<         baseListSize seqList 'baseList' STO                1 iterations         START                      \<<             @ 10 times, list 100 el: avg 0.48 s             baseList             1             \<<               \->               elementIn               \<<                 elementIn               \>>             \>>             DOSUBS             DROP             @"dosusbs"           \>>           TEVAL DTAG           'resListDosubs' STO+                      \<<             @ 10 times, list 100 el: avg 0.50 s             baseList             1             \<<               \->               elementIn               \<<                 elementIn               \>>             \>>             DOLIST             DROP             @"dolist"           \>>           TEVAL DTAG           'resListDolist'STO+                      \<<             @ 10 times, list 100 el: avg 0.93 s             1 baseListSize             FOR pos1               baseList               pos1               GET DROP             NEXT             @"for get"           \>>           TEVAL DTAG           'resListForGet' STO+                      \<<             @ 10 times, list 100 el: avg 1.19 s             baseList             1             1 baseListSize             START               GETI DROP             NEXT             DROP             DROP             @"start geti"           \>>           TEVAL DTAG           'resListStartGeti' STO+                      \<<             @ 10 times, list 100 el: avg 0.42 s             baseList             1 baseListSize 1 -             START               headList DROP             NEXT             HEAD DROP             @ "start headList"           \>>           TEVAL DTAG           'resListStartheadList' STO+                      \<<             @ 10 times, list 100 el: avg 0.96 s             baseList             1 baseListSize 1 -             START               DUP TAIL SWAP HEAD DROP               @www.hpmuseum.org/forum/thread-8209-post-74498.html#pid74498             NEXT             HEAD DROP             @ "start tail head"           \>>           TEVAL DTAG           'resListStarttailhead' STO+                      \<<             @ 10 times, list 100 el: avg 3.50 s             baseList             1 baseListSize             START               DUP HEAD DROP               -1 LROT             NEXT             DROP             @ "start lrot"           \>>           TEVAL DTAG           'resListStartLrot' STO+         NEXT                  "dosubs"         resListDosubs         "dolist"         resListDolist         "for get"         resListForGet         "start geti"         resListStartGeti         "start headList"         resListStartheadList         "start tail head"         resListStarttailhead         "start lrot"         resListStartLrot       \>>     \>>

Wikis are great, Contribute :)
06-12-2017, 09:41 PM
Post: #142
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 07:46 PM)pier4r Wrote:  So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist)
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)
...
Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

I'm a little surprised that the GET/GETI commands did that well, but I'd guess you'd start to see them slow down a bit as the list sizes grow.

LROT is actually fairly simple, but it does take some time. It basically determines the two sublists that need to be swapped based on the given parameter, makes the sublists, then reassembles them. I might be able to speed it up some with a slightly different approach, but I'm guessing it won't be a significant difference in the final timings. I should add this to my list of things to check, though.

The bulk of the time in the LROT loop is probably from LROT itself. DUP is very fast (it simply copies a pointer, not the actual data), and HEAD is pretty fast as well. My testing on lists of 100 items showed an average timing of .0336 seconds, so a loop of 100 iterations taking 3.36 seconds just for LROT alone would be expected. The remainder of the time for the other commands (and loop overhead) seems reasonable to me.

The internal representation of a list isn't very sophisticated. It's basically a prologue token, each object's data one after the other, and an epilogue token. So any commands that access individual objects within a list have to (literally) traverse/skip each and every object before the one in question in order to access it. In the case of embedded sublists, each element in them also has to be traversed. There's no way to skip over entire embedded sublists, as lists don't contain size information. Even getting the length of a list requires traversing all contained elements. So you can see where the longer a list is, the more time is required to deal with the list's elements.

HEAD is relatively fast because only the first element has to be accessed. TAIL can quickly skip the first element, but it still has to make a copy of the remainder of the list. So it's more sensitive to list size.

I haven't yet traced through DOSUBS and DOLIST to see how they work, but I suspect they do something similar to STREAM (which I have looked at) that allows relatively quick access to list contents by isolating one element at a time in the runstream. That method isn't available to UserRPL programs, as it requires manipulation of the return stack -- a technique that has to be executed very carefully to avoid blowing everything up.
06-12-2017, 09:51 PM (This post was last modified: 06-12-2017 09:52 PM by pier4r.)
Post: #143
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

Wikis are great, Contribute :)
06-12-2017, 10:19 PM
Post: #144
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 09:51 PM)pier4r Wrote:  For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

The method I want to test is similar to what I'm currently doing, but would involve loading the elements onto the stack from two different streams and then imploding the whole list. It may not actually be any faster than splitting a list into two pieces and reassembling them, but it's worth a try.
06-12-2017, 10:26 PM (This post was last modified: 06-13-2017 08:16 AM by pier4r.)
Post: #145
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(06-12-2017 10:19 PM)DavidM Wrote:  Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

Understood, I thought it was always quite quick. Then Lrot seems to be effective on a big chunk of rotations but not many little ones. Good to know.

The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the results.

Wikis are great, Contribute :)
06-13-2017, 12:43 AM
Post: #146
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 10:26 PM)pier4r Wrote:  The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the restults.

I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

Garbage Collections can be made worse by using certain techniques, though I must confess the reasons aren't always obvious. It could be that simply splitting a large list into two sublists is one of those techniques that causes problems. It doesn't make sense to me that it would be any worse than exploding everything then imploding it back, but the evidence speaks for itself!

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.
06-13-2017, 08:23 AM
Post: #147
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(06-13-2017 12:43 AM)DavidM Wrote:  I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

You saved me. The night is passed but the 50g is still working. Based on your measurements I would expect 13.5 hours for 10 cycles.

Impressive how headList dropped his efficiency and started to be not linear (so exploding a list does not help too) and impressive for + get. I remember now I tested it with 1000 elements and I was getting like 35 seconds. Even for it is not linear (one would expect 9 seconds, 10 times 0.9, not 35) but still only "5" times slower than the DOx commands. Also tail+head very quick.

Quote:The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.

Yes I guess special cases of an "handful" of elements rotated (I do not know a meaningful threshold, but maybe up to +10 , -10 ?) would make LROT really effective even for multiple calls.

Wikis are great, Contribute :)
06-13-2017, 10:06 AM (This post was last modified: 06-13-2017 11:49 AM by pier4r.)
Post: #148
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
In the meanwhile my 50g finished. Those are the results for 10 iterations over lists of 1000 elements (the same as the one from David, just to confirm the results. Wait not, there is one that does not fit)
"dosubs" avg { 7.85 }
"dolist" avg { 7.76 }
"for get" avg { 34.08 }
"start geti" avg { 54.86 }
wrong: "start headList" avg { 4.12 } (instead of 535 s. What's going on here? Surely replicating the test in different setups helps)
"start headList" avg { likely 535 as David tested } I found a bug and I checked the code for a list of 100 elements, it returns 1.66s on average (I corrected the older post). So likely it uses 530 seconds or more on 1000 elements. I do not have the time, at the moment, to let it run.
"start tail head" avg { 33.38 }
"start lrot" avg { 4867.04 }

I'll have to double check the headList result because it seems to good to be true. Moreover david reports 535 seconds, mine 4 seconds.

Edit: checked, indeed there was a bug.

Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

Wikis are great, Contribute :)
06-13-2017, 06:23 PM
Post: #149
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-13-2017 10:06 AM)pier4r Wrote:  ...Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

After spending more time than I care to admit trying alternative methods for LROT, I've come to the conclusion that any method that involves breaking the list apart into its constituent elements will eventually lead to a heart-stopping garbage collection if the function is called repeatedly in succession with a large-ish list as its argument. I was able to get it to the point where they were a bit less often, but it only delayed the inevitable.

So I've decided to try going the route I originally wanted to go in the first place, but thought might not be worth the hassle: I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine. It will be a good exercise that may have other benefits as well for the other functions I'm contemplating.

Regarding the GET performance, it occurs to me that I should probably temper my criticism of its performance. GET is better than PUT, owing to the fact that it's relatively quick to skip a series of objects when you don't actually have to explode them. But I still maintain that if you know you need to manipulate more than a couple of items in a list (or array, though they are a bit more efficient), it's better to break them apart and then reassemble them later than to loop a bunch of GET/PUT pairs.
06-13-2017, 10:00 PM
Post: #150
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Well from a completely ignorant point of view I somehow believe that consuming a list (for iterations) is somehow quick (indeed your tail head method is as fast as for + get). Just one has to extract elements properly. For this I asked you a sysrpl approach, because maybe there is a way.

Wikis are great, Contribute :)
06-14-2017, 05:40 AM
Post: #151
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-13-2017 06:23 PM)DavidM Wrote:  I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine.

First stab at the new version of LROT (LROT7 below) is promising:

\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{LROT} & 0.0259 & 0.0339 & 0.1006 & 0.1820 & 50 \\
\textbf{LROT7} & 0.0262 & 0.0299 & 0.0592 & 0.0945 & 50 \\
\hline
\end{array}

Timings are comparable to the original for smaller lists, but it scales nicely as the list sizes grow. And it's much nicer with regards to the memory footprint, in that it doesn't explode the list and rebuild it. Completed the 1000-element "stress test" (1000 loops with DUP/HEAD/etc.) in about 125 seconds.
06-14-2017, 08:04 AM (This post was last modified: 06-14-2017 08:06 AM by pier4r.)
Post: #152
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

Wikis are great, Contribute :)
06-14-2017, 08:57 AM (This post was last modified: 06-14-2017 12:08 PM by pier4r.)
Post: #153
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
@DavidM: another request if I may ask.

POS , as far as I know, returns the first matching position in a list.

What if I want to know all the positions that matches the element? I did, for one of the challenges, an helper routine. Do you find reasonable to develop one for your library?

Small argument by me: whether a routine it is good already in userRPL, it does not mean that it ready available for a user (which has to find it or develop it), that is the reason to have a "useful" library.

request:
Code:
 returnAllPosHelp "input: The built in POS, as far as I know, returns only the first match. L2: input list L1: element to search output L1: list of position where elment appears in list "      returnAllPos   \<<     { } @resultList     \->     @input     inputList     elementV     @local     resultList          \<<       inputList       \<<         \->         value         \<<           IF             value elementV ==           THEN             'resultList' NSUB STO+           END         \>>       \>>       DOSUBS       resultList     \>>   \>>

edit. another request, list contains
Code:
 listContainsHelp "input: 2: list L1  1: list L2 output: 1: { list of elements in L2 present in L1} remarks: - duplicates not checked. todo: - handle duplicates. If the same element occurs in L2 N times and it appears in L1 K times, with K <= N . Then the element will appear in the result K times, not N. "           listContains     @it seems to work     \<<       {} "resList" DROP              \->       @input       inL1       inL2              @var       resList              \<<         {} @handle empty result                inL2         1         \<<           \->           @input           element                      \<<             inL1 element POS 0 \=/             element             IFT           \>>           \>>         DOSUBS                  IF           DUP SIZE 0 >         THEN           @non empty result           @clear the list before           +         END       \>>     \>>

request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.

edit. Also #36

Code:
 c36vaV1     @given a list made of sublists     @returns the sublists (positions) that contain a given element          @it seems working     \<<       {} "resList" DROP         @in the case it will be the result when no match is found              \->       @input       inL1       element              @local var       @L1size       resList       \<<                  1 inL1 SIZE         FOR index           inL1 index GET  @get sublist           element POS @get the position           IF             @if the element is present (at least once)             DUP 0 \=/           THEN             @at the position to the result             'resList' index STO+           END           DROP @clean the stack         NEXT                  resList       \>>     \>>

edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

Wikis are great, Contribute :)
06-14-2017, 11:49 AM
Post: #154
 Werner Senior Member Posts: 514 Joined: Dec 2013
RE: Programming puzzles: processing lists!
ALLPOS

Code:
\<<   \-> o   \<<     1.     \<< o == NSUB IFT \>>     DOSUBS   \>> \>>

or, when no match returns an empty resultlist:

Code:
\<<   \-> o   \<<     {} SWAP     1.     \<< o == NSUB IFT \>>     DOSUBS   \>>   IF DUP SIZE THEN + END \>>

Cheers, Werner
06-14-2017, 02:34 PM
Post: #155
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 08:04 AM)pier4r Wrote:  Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

I agree with you about the multiple rotations, which is part of the reason I went ahead and did this.

To be fair, this is (for a 50g) a fairly extreme situation due to the list size. Exploding a list and then rebuilding it leaves behind unreferenced objects; the number of discards will be (at a minimum) equal to the number of objects in the list + the original list. When you do that rapidly in succession, the "garbage" builds up quickly. It's inevitable that a GC will take place, and when it does, it has to locate/flag-objects-for-disposal/re-compress all of the space they were inhabiting.

The changes I made still leave a large block of memory disposed, but it's contiguous and easily "skippable". When watching a loop make 1000 calls to LROT (v7) operating on a list of 1000 elements, you can barely discern when the GCs occur. The previous version left 1000 disposable objects behind every iteration, so the GCs would lock up the system for a painful period every time they happened.

I should note that this phenomenon is not unique to my library; any activity (whether built-in or user-programmed) that explodes/implodes large lists will be vulnerable to this issue.
06-14-2017, 03:27 PM
Post: #156
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 08:57 AM)pier4r Wrote:  @DavidM: another request if I may ask.
...
request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.
...
edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

I think of this "working project" as a collaborative effort, and I'm happy to consider all suggestions for additional functions/commands. It continues to be a good exercise for me to consider the application of list processing in solving problems as opposed to my more "iterative" inclinations.

I've been somewhat concerned that showing my earlier timing comparisons with GoferList functions would be perceived as my wanting to replace it (or even "compete" with it). That definitely wasn't/isn't my intent. It seemed like a good benchmark for comparison with similar functions that I'd already created, so I thought it would make sense to show the data that way.

GoferList appears to have been originally created with the idea that it would replicate known list functions from the Haskell language, so I'm guessing that the original developers were less concerned about documenting the commands and only felt the need to provide the minimum needed to use the commands in an RPL context. They probably figured that it's main appeal would be to people who already knew what the functions did, or would seek the meaning in other ways.

I definitely see my library as a complement to GoferList, even though there is a small amount of overlap. If I'm to implement more functions, I'd prefer to focus on those things that aren't already available in GoferList (or trivial to implement). As an example, many of the GoferList commands are designed to apply a user-defined function to a process. I have no desire to replicate that sort of functionality, as I don't think I could really add anything useful to those commands. Gilles' suggestion of a DOPERM command would represent new functionality that definitely would add value (and isn't trivial), so it's high on my list to investigate. So that's more the type of thing that interests me at present.

I'll add your recent suggestions to my list of things to ponder, as I can see where those functions would be useful in a variety of contexts.
06-14-2017, 03:38 PM
Post: #157
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 11:49 AM)Werner Wrote:  ...
Code:
...   { } SWAP ...   IF DUP SIZE THEN + END

Nice, Werner. That's a great way to deal with the "no list returned" issue!
06-14-2017, 06:02 PM (This post was last modified: 06-14-2017 06:04 PM by pier4r.)
Post: #158
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Werner nice input, although your very usage of the stack sometimes is not so easy to follow if one loses track of what is on the stack (like the fact that you collect only one input in a variable, the other is on the stack). I prefer something that may be bigger but easier to read if I did not touch it for long.

Anyway, the #35 , that with "for + get" is feasible (still, I think that even with for + get the #20 would be quite more demanding), seems working.

Actually I am not sure I tested all the corner cases so if you want to play along, do it.
It uses, I think, the library of david and also goferlist in case some commands were missing (but I avoided to replicate them)

The #35 requires the #36 and an helper.

If you have tips were I can improve (keeping things readable), let me know.

For the timings, well, I'll do if there is a bit of competition.

Code:
 c35vaV1     @check if an input list with a certain structure makes a balanced binary tree     @requires list library of DavidM and goferlist          @for the test done it seems working.     \<<              @plan:        @ - first finding the root that is the only sublist of the list containing       @   0. Also this method of search will be crucial for all the other       @   cases. So it is like a new processing list challenge:       @   "return the positions of all the sublists of a list containing the given       @   object"       @ - put the position in LI (list input)       @   of the object containing 0 in a separated list of "checked       @   positions", called LCP       @ - put the root in a separated list to consume to traverse the tree,       @   called LTT       @ - put the height of the current element added to LTT in a list of       @   heights, LH. Note that the height in LH should match the position of the       @   root in LTT       @ - consume the first element (the root) from the list LTT.       @   (since LTT has a relationship with LH, a way to consume it is       @   to increment a counter after reading the element)       @   check the positions of all the sublists containing it in LI       @   (should be max 3, otherwise the tree is invalid)       @ - put the destinations reached by the root , that have positions       @   not present in LCP in LTT       @ - put the heigths of those destinations in LH, with same positions       @   as the destinations in LTT. Of course the heights are equal to       @   the parent height (the root) plus one.       @   We know who is the parent because we know which elements from LTT we are       @   consuming.       @ - put the returned positions in LCP (if you do this step before,       @   you cannot use to discriminate new destinations)       @ - generic step       @   - Consume the next element E from LTT. Check all the sublists in LI that       @     contains it. As usual, it should be max 3, of which max 2 sublists       @     should be new (that is, their position is not in LCP). otherwise       @     the tree is invalid (can still be invalid in other ways though)       @   - put the destinations of the sublists where E appears, sublists that       @     have positions not in LCP, in LTT.       @   - collect the height of E from LH, and add plus one and put the heights of the       @     new destinations in LH with positions relative to the position just added       @     in LTT       @   - add the positions retrieved before that are new in LCP       @   - check. A node that has a single children (so only one destination)       @     cannot have the children having children as well. So if given an element E       @     only one destination is added, a check has to be done and        @     (a) the destination should appears only once in LTT       @     (b) searching for sublists with the destination in LI        @         should return only one match that should be already in LCP in       @         terms of positions       @     otherwise the tree is invalid.       @   - check. For the height. Since the procedure in theory is devised to       @     explore the tree layer by layer, it means that every children has       @     the height of the parent, plus 1. (because we add children when we       @     expand a parent). Now when we have a node with no children, that is       @     a leaf and we save the __minimum__ leaf height, then we continue to       @     expand the rest.       @     If we ever get a node that is +2 than the minimum leaft height       @     then the tree is invalid because not balanced.              0 "inL1Size" DROP       {} "LExtractPos" DROP       {} "LNodes" DROP       1 "indexElToExpand" DROP       {} "LNodesHeight" DROP       0 "minHeight" DROP       1 "parentNode" DROP       0 "parentNodeHeight" DROP       {} "LTemp" DROP       0 "LTempSize" DROP       {} "LTemp2" DROP       {} "LTempSublist" DROP       0 "tempScalar" DROP       0 "isNotValid" DROP              \->       @input       inL1              @localVar       inL1Size       LExtractPos       LNodes       indexElToExpand       LNodesHeight       minHeight       parentNode       parentNodeHeight       LTemp       LTempSize       LTemp2       LTempSublist       tempScalar       isNotValid       \<<         inL1 SIZE 'inL1Size' STO                  @find the root         inL1 0 c36vaV1 'LTemp' STO                  IF           @if more than one node with 0 is returned           @remember no duplicates allowed so we cannot have 2 roots           LTemp SIZE 1 \=/         THEN           1 'isNotValid' STO         END                  @check if the sublist in the position of the root is in the proper         @structure         IF           @if the tree is still valid           isNotValid 0 ==                      @but the sublist is not           inL1 LTemp HEAD GET 'LTempSublist' STO           LTempSublist 0 c35vaV1isSublistValid           NOT                      AND         THEN           1 'isNotValid' STO         END                  @if we are here, the root is valid         @ so put the root in the list of elements to expand         'LNodes'          LTempSublist 2 GET STO+         @the add the height of the element that we will expand         @the height is equal to the parent +1 in this case the root has height         @ 0. The position should be the same of the position in the nodes         'LNodesHeight' 0 STO+                  @then put the sublists' positions in the list telling us         @which ones have we already extracted         'LExtractPos' LTemp STO+                  @we set the minimum height to a value that unlikely will be matched         inL1Size 'minHeight' STO                  @now let's proceed with the rest of the nodes         WHILE           @the tree is still valid           isNotValid 0 ==             @it does not need to be checked for every action always,             @since isNotValid can get only 1, it dosn't need many checks.             @when it fails, will be reported at the next iteration                        inL1Size indexElToExpand \>=           AND         REPEAT           @ we take the next parent node           LNodes indexElToExpand GET 'parentNode' STO           LNodesHeight indexElToExpand GET 'parentNodeHeight' STO                      @we get the positions of sublists containing the parent node           inL1 parentNode c36vaV1 'LTemp' STO                      @the sublists should be at least 1 and not more than 3           LTemp SIZE 'LTempSize' STO           IF             LTempSize 0 <             LTempSize 3 >             OR           THEN             1 'isNotValid' STO           END                      @#############           @LTempSize 1 ==                      @if the sublist is just one, the parent node is a leaf           @we can set if this leaf has the minium height so far           @but we need to check that the returned sublist position is already           @one checked           IF             LTempSize 1 ==           THEN             IF               @if the sublist position is not what we got already               LExtractPos LTemp HEAD POS 0 ==             THEN               1 'isNotValid' STO             END                          IF               @if the height of the node is smaller than the minimum               @set it as new minimum               minHeight parentNodeHeight >             THEN               parentNodeHeight 'minHeight' STO             END                          IF               @if the height of the leaf is 2 more than the minimum heght,               @then the tree is invalid               parentNodeHeight minHeight 1 + >             THEN               1 'isNotValid' STO             END           END                      @#############           @LTempSize 2 ==                      @if the sublist returns 2. It means that there is the parent           @and a child, but we need to check that this is a child           @and if it is a child, it was not extracted before and           @it won't have further children as well            IF             LTempSize 2 ==           THEN             @if we have one position known and the other unknown,             @we need to extract the unknown position (where the parent connects to a child)             LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position                          IF               @the positions extracted should be one known and one unknown               @so the unknown should be 1               LTemp2 SIZE 1 \=/             THEN               1 'isNotValid' STO             END                          inL1 LTemp2 HEAD GET @get sublist             'LTempSublist' STO                          IF               LTempSublist parentNode c35vaV1isSublistValid               NOT                              @destination already in the destinations (a loop)               LNodes                LTempSublist 2 GET                POS 0 \=/                              AND             THEN               1 'isNotValid' STO             END                          @so here the additional list is valid             @we have to expand it             'LNodes' LTempSublist 2 GET STO+                           'LNodesHeight' parentNodeHeight 1 + STO+                          'LExtractPos' LTemp2 STO+                          @if there is only a child, this child cannot have more children             @this has to be checked now otherwise the script loses the "memory"             @that there is only one child node             IF               @So now we have in how many sublists the destination/child node is present               @this should be exactly one and already extracted, equal to the last               @addition to LExtractPos               inL1 LTempSublist 2 GET                c36vaV1 LTemp2 \=/             THEN               1 'isNotValid' STO             END           END                      @#############           @LTempSize 3 ==                      @if the sublist returns 3. it means a parent and           @ two children. Those have to be valid lists and that's it           IF             LTempSize 3 ==           THEN             LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position                          IF               @the positions extracted should be one known and two unknown               @so the unknown should be 2               LTemp2 SIZE 2 \=/             THEN               1 'isNotValid' STO             END                        1 2             FOR index2                             @get sublist               LTemp2 index2 GET 'tempScalar' STO               inL1 tempScalar GET               'LTempSublist' STO                              @verity it is valid               IF                 LTempSublist parentNode c35vaV1isSublistValid                 NOT                                  @destination already in the destinations (a loop)                 LNodes                  LTempSublist 2 GET                  POS 0 \=/                                  AND               THEN                 1 'isNotValid' STO               END                              @add the destination to the nodes to expand               'LNodes' LTempSublist 2 GET STO+                             @add the height of the node just added               'LNodesHeight' parentNodeHeight 1 + STO+             NEXT                          @add the extracted position             'LExtractPos' LTemp2 STO+           END                      1 'indexElToExpand' STO+         END                  isNotValid NOT       \>>     \>>          c35vaV1isSublistValid     @ given a list (sublists of another)     @ assumes that the list contains 2 elements     @ of which the one passed as argument is the source, so the first one.     @requires list library of DavidM          @it seems working     \<<       1 "isValid" DROP            \->       @input       inL1       source              @local var       isValid              \<<         IF           inL1 SIZE 2 \=/         THEN           0 'isValid' STO         END                  IF           isValid 1 ==         THEN           IF             inL1 source POS 1 \=/             inL1 source LCNT 1 \=/             OR           THEN             0 'isValid' STO           END         END                  isValid       \>>     \>>          c36vaV1     @given a list made of sublists     @returns the sublists (positions) that contain a given element          @it seems working     \<<       {} "resList" DROP         @in the case it will be the result when no match is found              \->       @input       inL1       element              @local var       @L1size       resList       \<<                  1 inL1 SIZE         FOR index           inL1 index GET  @get sublist           element POS @get the position           IF             @if the element is present (at least once)             DUP 0 \=/           THEN             @at the position to the result             'resList' index STO+           END           DROP @clean the stack         NEXT                  resList       \>>     \>>

Wikis are great, Contribute :)
06-15-2017, 06:21 PM
Post: #159
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
I thought that it might be worth a few more bytes to have two more special-purpose commands that could be wrapped around the same core that's at the heart of LROT: LRLL (List Roll) and LRLLD (List Rolldown). These are functionally equivalent to 1 LROT and -1 LROT, but faster since the amount of rotation doesn't have to be computed from an argument. It also seemed to me that a rotation of 1 or -1 would be common enough to warrant a separate command for those purposes.

The names were chosen to coincide with similar RPL stack-based functionality. LRLL does the same thing as
Code:
\<<    LIST\-> \-> 'lsize'    \<<       lsize ROLL lsize \->LIST    \>> \>>

LRLLD is the same, just replace ROLL with ROLLD.
06-15-2017, 06:30 PM
Post: #160
 Johnny Knoxville Junior Member Posts: 2 Joined: Jun 2017
RE: Programming puzzles: processing lists!
Reading the replies of all experts is just fascinating.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)